我不知道那个算法叫什么名字。。
先说说什么是强连通分量,也就是在这个分量中,所有的点都相互可达~~
当明白什么是强连通分量的时候,就可以看一个图说出他们的强连通分量了。
算法:
1。当深度搜索一棵树的时候,如果第一次搜索到某个强连通分量的点时,这个点我们记录为a,那么,经过一系列深度搜索后,这个连通分量里的所有的点的完成时间,即后序遍历序号,即算法导论里面说的变成“黑色”的点地时间,一定是最长的。因为深度搜索的特性决定的。
2。我们把一个连通分量的边变成反向的,它同样还是连通的。
应用这个,再结合算法,算法说 先正dfs原图,然后按照后序便利需要从大到小dfs原图的逆图。
其实就是根据上面2个原理。要从后序便利序号来dfs原图是抓住每个连通分量的a,这样不会漏掉连通分量,而把图倒过来以后,连通性仍然保持,再dfs就可以了。