まさに文字通り、強連結成分分解をしてください、という問題ですね。そしてこの問題は、Yosupo Judge の Strongly Connected Components が元になっているようです。
問題概要
頂点 辺の有向グラフが与えられる。
番目の辺は である。このグラフは単純とは限らない。 このグラフを強連結成分分解し、トポロジカルソートして出力してください。
制約
強連結成分分解 (SCC) とは
強連結成分分解 (Decomposition of Strongly Connected Components, SCC) とは、有向グラフにおいて 「お互いに行き来できる頂点を同じグループになるように頂点をグループ分けする」ことをいいます。 たとえば、次の有向グラフを見てみましょう。
- 頂点 0, 2 は互いに行き来できます
- 頂点 0 → 頂点 2:直接行けます
- 頂点 2 → 頂点 0:頂点 3 を経由して行けます
- 頂点 0, 4 は互いに行き来はできません
- 頂点 0 から頂点 4 へは行けます
- しかし、頂点 4 からは頂点 0 へ行けません
このグラフは、「互いに行き来できる関係」によってグループ分けすると、下図のようにグループ分けできます。
グループ A, B, C, D, E の内部の頂点たちは互いに行き来できます。しかし、異なるグループの頂点間は、一方から他方に行けることはあり得ますが、互いに行き来することはできません。
そして、各グループを新たな頂点とすることで、新たなグラフが作れます! この新たなグラフでは、グループ間の辺を次のように張ります。
グループ 内のある頂点から、グループ 内のある頂点に辺があるとき、グループ からグループ へと辺を張ります。
このとき、仮にグループ からグループ への辺が張られているときに、グループ からグループ へと辺が張られることは絶対にあり得ないということに注意しましょう。なぜなら、もしそうなら、グループ とグループ は自由に行き来できることとなり、本来は同じグループだということになってしまうためです。
ゆえに、新たに作られるグラフは DAG (Directed Acyclic Graph) となります。DAG とは「閉路のない有向グラフ」のことです。
ACL の強連結成分分解ライブラリ
さて、AtCoder の強連結成分分解ライブラリは、次のインターフェースになっています。
vector<vector<int>> graph.scc();
これは、次の条件を満たすような、「頂点のリスト」のリストを返します。
- 各リストは強連結成分に対応します
- 各リストは、強連結成分分解してできる DAG のトポロジカルソート順にソートされています
このライブラリは の計算量で動作します。アルゴリズムの詳細は、たとえば次の記事などを参照。
また、ACL の SCC ライブラリの公式ドキュメントも参照:
https://atcoder.github.io/ac-library/production/document_ja/scc.html
AC コード
ACL の SCC ライブラリを使って AC しました。
#include <bits/stdc++.h> #include <atcoder/scc> using namespace std; using namespace atcoder; int main() { int N, M; cin >> N >> M; // SCC を適用するためのグラフを構築する scc_graph G(N); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; G.add_edge(u, v); } // SCC auto scc = G.scc(); // 出力 cout << scc.size() << endl; for (auto list : scc) { cout << list.size(); for (auto v : list) cout << " " << v; cout << endl; } }
自前ライブラリでも AC
#include <bits/stdc++.h> using namespace std; struct SCC { using Edge = int; using SGraph = vector<vector<Edge>>; // input SGraph G, rG; // result vector<vector<int>> scc; vector<int> cmp; SGraph dag; // constructor SCC(int N) : G(N), rG(N) {} // add edge void addedge(int u, int v) { G[u].push_back(v); rG[v].push_back(u); } // decomp vector<bool> seen; vector<int> vs, rvs; void dfs(int v) { seen[v] = true; for (auto e : G[v]) if (!seen[e]) dfs(e); vs.push_back(v); } void rdfs(int v, int k) { seen[v] = true; cmp[v] = k; for (auto e : rG[v]) if (!seen[e]) rdfs(e, k); rvs.push_back(v); } // reconstruct set<pair<int,int>> newEdges; void reconstruct() { int N = (int)G.size(); int dV = (int)scc.size(); dag.assign(dV, vector<Edge>()); newEdges.clear(); for (int i = 0; i < N; ++i) { int u = cmp[i]; for (auto e : G[i]) { int v = cmp[e]; if (u == v) continue; if (!newEdges.count({u, v})) { dag[u].push_back(v); newEdges.insert({u, v}); } } } } // main void solve() { // first dfs int N = (int)G.size(); seen.assign(N, false); vs.clear(); for (int v = 0; v < N; ++v) if (!seen[v]) dfs(v); // back dfs int k = 0; scc.clear(); cmp.assign(N, -1); seen.assign(N, false); for (int i = N - 1; i >= 0; --i) { if (!seen[vs[i]]) { rvs.clear(); rdfs(vs[i], k++); scc.push_back(rvs); } } // reconstruct reconstruct(); } }; int main() { int N, M; cin >> N >> M; // SCC を適用するためのグラフを構築する SCC scc(N); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; scc.addedge(u, v); } scc.solve(); // 出力 cout << scc.scc.size() << endl; for (auto list : scc.scc) { cout << list.size(); for (auto v : list) cout << " " << v; cout << endl; } }