Strongly Connected 强连通性
定义 如果两个顶点 v 和 w 是互相可到达的,则称它们是强联通的(Strongly Connected). 如果一幅图中,任意两个顶点都是强连通的,则称这幅有向图也是强连通的。
Kosaraju Algorithm.
计算无向图的强联通分量只需要加一点点内容就好了。
kosaraju 和 cc 仅仅只有一点不同。 首先给定一个有向图G,计算它的反向图。 然后对它的反向图进行逆后序排列。 在G中进行DFS,但是要按照刚刚的逆后序来访问。
Last updated
Was this helpful?