Tarjan强连通分量与缩点
目录
之前就没有很搞懂dfs搜索树的顺序,这次好好搞一下。
概念
强连通:两个点互相可达称为强连通 连通分量:一个集合中的顶点互相可达,称为连通分量 强连通分量:每个集合中最大的连通分量。
dfs搜索树上边分为四大类(jls的集训队论文也提到了)
- 树枝边(父节点与子节点之间的边、特殊的前向边)
- 前向边(每个点到后代的点)
- 后向边(每个点到祖先的点)
- 横叉边(往其它分支搜索的时候产生)
判是否在强连通分量中:
- 存在后向边指向祖先节点
- 先走到横叉边,再走到祖先。
Tarjan
引入时间戳的概念判断在dfs中被搜到的顺序(是否和dfs序是一个东西?)
对每个点定义两个时间戳:
- dfn[u]遍历到u的时间戳
- low[u]从u开始走,所能遍历到的最小时间戳
u是其所在的强连通分量的最高点,等价于dfn[u]==low[u]
如果还能往上走,就说明强连通分量还没搜完。
|
|
缩点
|
|
连通分量编号递减的顺序一定是拓扑序,不需要缩点后再写拓扑排序
感性认识一下,编号越大的越靠上,那么从大到小是拓扑序也挺合理的(