SCC = strong connected component. 即强连通分量。
In the mathematical theory of directed graphs, a graph is said to be strongly connected or diconnected if every vertex is reachable from every other vertex the strongly connected components or diconnected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. (wikipedia)
强连通分量是指有向图的一个子图,在该子图中所有的结点到其他结点都是可达的。
Kosaraju‘s algorithm (also known as the Kosaraju–Sharir algorithm)
Is a linear time algorithm to find the strongly connected components of a directed graph.
It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.
Traverse edges in the backward direction to get the transpose graph.
DFS the transpose graph you get, store the visit sequence in a stack
DFS the original graph using the stack.
O(V+E) if you are using the adjacent list.
https://www.cnblogs.com/nullzx/p/6437926.html 这篇文章里有实例分析。