强连通分量 2024-10-02 1:14 | 118 | 0 | 笔记 952 字 | 16 分钟 强连通的定义是:有向图 G 强连通是指,G 中任意两个结点连通。 强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图。 Tarjan算法 对于一个连通块,以任意节点作为根节点进行深度优先搜索(DFS)。将节点的深度优先搜索序记为 dfn[x],将节点能够通过返祖边到达的最早节点的深度优先搜索序… tarjan图论强连通分量