【競プロ覚書】SCC
本日のお題はSCC(StronglyConnectedComponents、強連結成分分解)です。有向グラフにおいて、相互に行き来できる成分ごとに分解できるものです。計算量はO(V+E)
【22 日目】
— E869120@本発売 (@e869120) 2021年4月22日
昨日の解説と今日の典型問題です。今日は立方体の問題です!!!
なお、AtCoder ジャッジへの問題追加は 15 時頃を予定しています。(入力形式・入出力例は GitHub を参照のこと) #競プロ典型90問 pic.twitter.com/mHRaIeiZWY
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(); } };