前言
tarjan 弄出来了 LCA 和 tarjan,这里主要讲了一下 tarjan(LCA 太简单了懒得写)。
关于 tarjan 大概就是强连通分量,缩点和割点,感觉挺有用的,学图论大概必备吧。
强连通分量
即在一个有向图中两个点可以互相到达,那么称这个图为强连通图。
说实话这个直接 tarjan 求就可以了。
tarjan 算法思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树。那么其实只要确定每个强连通分量的子树的根,然后根据这些根从树的最低层开始,一个一个的拿出强连通分量即可。那么剩下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。 —— 百度