強連結成分分解
強連結成分分解は
Strong Connected ComponetsというSCCコンポーネントに分解するアルゴリズムである。
有向グラフは、お互いに行き来できるグループごとに分割することができる。
https://gyazo.com/f59054bd95264e056404c4f7e06ff2dc
アルゴリズムとしてはまず
1. ある頂点からDFSをする。このとき、DFSの帰りがけで頂点をorderに保存する。
2. 頂点を帰りがけ順で保存したので、orderを後ろ側から逆にみると、先に見た順となっている。
3. 先にみた順であるため、この順番でもう一度、逆辺を作ったグラフでDFSを行い、まだ訪問していないものはcompに保存していく。
上記が成り立つ理由をいかに記述する。
まず、SCCではお互いに行き来する頂点たちを一グループとする。
よって、逆辺のみのグラフでも当然行き来できるはずである。
よって、逆辺を利用してまだ訪問していないものはそのグループとしてよい。
次に、１のDFSを帰りがけで頂点を保存する理由だが、帰りがけで保存をすれば、後ろ側から見ると最初から見ていった頂点となっている。よって、トポロジカルソートのような順番になっている。
そして、この１のDFSを始めた順番に結局似ているので、orderの逆順から頂点を見ていくと、まずこの頂点からいける頂点たちは当然逆辺でたどり着けるということは元の辺でもたどり着けるため、同じグループに所属する。
つぎにひとしきりグループを作ったあと、まだグループに入っていない頂点は新しいグループとしてRDFSをするが、このとき、当然１で帰りがけでトポロジカルソートをしているため、すでにグループとなっているものにアクセスすることはない。（アクセスできてもSCCというグループとしては同じでない。もしSCCなら前回のグループ形成で自分も含まれているためである。）
含まれていないとういことは、自分のグループたちからは、既にできているSCCグループと共通のグループではない。
よって、このようにやっていけば、SCCを構成できる。
https://gyazo.com/0ac899a09b387cbcfe6fcdf835518bf1
上記のように、グループ同士は、１で帰りがけで保存しているためトポロジカルソートになっており同じcompの値同士内は１グループで、それ以外はトポロジカルソートで、必ず昇順となっている。
verify
使い方
scc[i]は頂点$ iが属するグループIDが入っている。
グループ数はgt.size()で取れる。
gt[i][j]はグループiからグループjに対して、SCC後の有効辺があることを示している。
ただ、多重編である。
code:cpp
int main() {
int V, E;
cin >> V >> E;
UnWeightedGraph graph(V), buff;
for (int i = 0; i < E; i++) {
int s, t;
cin >> s >> t;
}
StrongConnectedComponents<UnWeightedGraph> scc(graph);
scc.build(buff);
int Q;
cin >> Q;
while (Q--) {
int s, t;
cin >> s >> t;
if (sccs == scct) cout << 1 << endl; else cout << 0 << endl;
}
return 0;
}
code: cpp
template<typename G>
struct StrongConnectedComponents {
/// @bried graph SCCする元グラフ
const G &graph;
int V;
/// @brief graph SCC用の内部グラフ
UnWeightedGraph go_g, rv_g;
/// @brief comp compv = vの所属するSCCの番号 トポロジカル順 vector<int> comp;
/// @brief dfs用
vector<bool> used;
/// @brief dfsの帰りがけ順
vector<int> order;
StrongConnectedComponents(G &graph) :
graph(graph), V(graph.size()), go_g(V), rv_g(V), comp(V, -1), used(V, false) {
for (int i = 0; i < V; i++) {
go_gi.emplace_back((int) e); }
}
}
/// @brief 頂点vの所属するSCCのIDのを返す
int operator[](int v) {
}
void dfs(int v) {
for (auto to: go_gv) dfs(to); order.emplace_back(v);
}
void rdfs(int v, int cnt) {
for (auto to: rv_gv) rdfs(to, cnt); }
vector<int> get_comp() const {
return comp;
}
/// @param gt 参照で空グラフを与える gtSCCIDが繋がる他の頂点 void build(UnWeightedGraph >) {
for (int i = 0; i < V; i++) dfs(i);
reverse(order.begin(), order.end());
int cnt = 0;
for (auto v: order) if (compv == -1) rdfs(v, cnt), cnt++; gt.resize(cnt);
for (int i = 0; i < V; i++) {
if (x == y) continue;
}
}
}
};