仍然暂时没有什么内容。

强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图。

kosaraju算法

深搜遍历

选择最晚访问的节点,对G的反向图进行遍历,能遍历到的所有点就构成一个SCC,删去。

tarjan算法

生成树:如果连通图G的一个子图是包含G的所有结点的树,则称该子图为G的生成树<=>G的生成树是G的一个无环子集T$\subseteq$E,且T连接了G的所有节点。

DFS生成树:树边(tree edge)、返祖边(back edge)、横叉边(cross edge)、前向边(forward edge)

考虑DFS生成树和强连通分量之间的关系 强连通分量的第一个在树中的节点很重要

DFN[u]时间戳 次序编号

LOW[u]在搜索树中 最小子树的根

新点的low=dfn

储存强连通分量的容器是栈