跳至主要內容
有向图的强联通分量(SCC)Tarjan算法

有向图的强联通分量(SCC)Tarjan算法O(n+m)

强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图。
下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。
image.png

DFS生成树:
image-20230725134818030


全民制作人ikun大约 7 分钟Algorithm图论Algorithm图论Tarjan强联通分量