有向图的强联通分量(SCC)Tarjan算法O(n+m)
强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图。
下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。
DFS生成树:
大约 7 分钟
强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图。
下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。
DFS生成树: