src/Graph/StronglyConnectedComponents.hpp
概要
Kosaraju’ algorithm(https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm)による強連結成分分解。O(E + V)。
2回dfsを行う。
1回目のdfsでpost-orderを記録。
2回目はそれの逆順に始点を変えてdfsを行い、到達可能な頂点集合は同じ強連結に属することがわかる。
Required by
Verified with
Code
Back to top page