強連結成分分解
有向グラフにおいて互いに行き来できるグループ…強連結成分に分解することを強連結成分分解という。略してSCC。仕組みについては高校数学の美しい物語に書いてある。
https://gyazo.com/44301818623adbf5477da15bc244709f
https://gyazo.com/c7e553584a1dfe7a613ddcf1beefc2a5
写しただけというか元のコードが良すぎて改良とかできないのでコメント書くだけになってしまう…
code:強連結成分分解.cpp
// 強連結成分分解をします。scciで頂点iが何番目の成分に含まれているかが分かる。 // StronglyConnectedComponents(グラフ);のあと、build(重みなしグラフ);をする。
template <typename G>
struct StronglyConnectedComponents {
const G &g;
UnWeightedGraph ng, rg; // normal-graphとreversed-graph
vector<int> compo, order, used; // compo…頂点がどの成分に属しているか、order…帰りがけ順で何番目か
StronglyConnectedComponents(G &g) : g(g), ng(g.size()), rg(g.size()), compo(g.size(), -1), used(g.size()) {
for (int i = 0; i < g.size(); i++)
ngi.emplace_back((int)t); rg(int)t.emplace_back(i); // 逆辺 }
}
// []で聞かれたときは成分番号を返す
int operator[](int k) { return compok; } void dfs(int now) {
for (auto to : ngnow) dfs(to); order.emplace_back(now);
}
void rdfs(int now, int count) {
// used代わりに結果を入れていく
if (componow != -1) return; for (auto to : rgnow) rdfs(to, count); }
void build(UnWeightedGraph &ret) {
// 普通にDFS、辺の向きを変えてもう一度DFS
for (int i = 0; i < ng.size(); i++) dfs(i);
reverse(order.begin(), order.end());
int group = 0;
for (auto i : order)
if (compoi == -1) rdfs(i, group), group++; // 縮めたグラフを構築する
ret.resize(group);
for (int i = 0; i < g.size(); i++) { // 全ての辺について
int s = compoi, t = compoto; if (s != t) rets.emplace_back(t); }
}
}
};