【競プロ覚書】SCC

本日のお題はSCC(StronglyConnectedComponents、強連結成分分解)です。有向グラフにおいて、相互に行き来できる成分ごとに分解できるものです。計算量はO(V+E)

DFSを2回やることがポイントで、1回目は行き止まりになった順番に番号を記録、2回目はその頂点の順番で枝の向きを逆にしたグラフに対してDFSをします。
詳しくは下のリンクで
強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語

コード

使いやすいようにクラス化しました。
AddEdge(a, b) : A→Bの辺を追加
isSame(u, v) : 頂点uと頂点vが同じ強連結成分に含まれているか
GetGroup(u) : 頂点uの含まれている成分の番号を取得
GetGroup_num() : 全てで幾つの強連結成分に分かれているかを取得
GetGroup_size(i) : 成分iに含まれている頂点の数を取得

class StronglyConnectedComponents
{
private:
    vector<bool> used;
    vector<int> G[1 << 18];
    vector<int> H[1 << 18];
    vector<int> I;
    vector<int> group;
    vector<vector<int> > group_component;
    int group_num;

    void dfs1(int pos)
    {
        used[pos] = true;
        for(int i : G[pos]){
            if(used[i] == false) dfs1(i);
        }
        I.push_back(pos);
    }

    void dfs2(int pos, int _group)
    {
        used[pos] = true;
        group[pos] = _group;
        group_component[_group].push_back(pos);
        for(int i : H[pos]){
            if(used[i] == false) dfs2(i,_group);
        }
    }
public:
    void AddEdge(int from, int to)
    {
        G[from].push_back(to);
        H[to].push_back(from);
    }

    void Init(int vertex_num)
    {
        group.assign(vertex_num+1, -1);
        used.assign(vertex_num+1, false);
        group_num = 0;
        for(int i=1;i<=vertex_num;i++){
            if(used[i] == false) dfs1(i);
        }
        reverse(I.begin(), I.end());
        used.assign(vertex_num+1, false);
        for(auto &i : I){
            if(used[i] == true) continue;
            group_component.push_back(vector<int>());
            dfs2(i,group_num);
            group_num ++;
        }
    }

    bool isSame(int u, int v)
    {
        return group[u] == group[v];
    }

    int GetGroup(int u)
    {
        return group[u];
    }

    int GetGroup_num()
    {
        return group_num;
    }

    int GetGroup_size(int _g)
    {
        return group_component[_g].size();
    }
};