从缩点到圆方树

一些概念

连通：无向图中的任意两点都可以互相到达。

强连通：有向图中的任意两点都可以互相到达。

连通分量：无向图的极大连通子图。

强连通分量：有向图的极大强连通子图。

DFS 生成树：对一张图进行深度优先遍历得到的生成树。

树边：在 DFS 生成树上的边。

前向边：由子树的根连向子树内的非树边。

返祖边：由结点连向其祖先的边。

横叉边：除上面三种以外的边。

割点：无向连通图删除某个点和以其为端点的所有边后，若图不再连通，则该点是图的一个割点。

割边（桥）：无向连通图删除某条边后，若图不再连通，则该边是图的一条割边。

点双连通图：不存在割点的无向连通图。

边双连通图：不存在割边的无向连通图。

点双连通分量：无向连通图的极大点双连通子图。

边双连通分量：无向连通图的极大边双连通子图。

缩点（求强连通分量）

对于点 \(u\)，记录两个信息 \(dfn_u\) 和 \(low_u\)。

\(dfn_u\) 表示时间戳，即点 \(u\) 是第几个被遍历到的。

\(low_u\) 表示从点 \(u\) 开始，经过的边的两个端点均处于未找出的强连通分量中，所能到达的最小时间戳。

在 DFS 的过程中，将经过的点塞进一个栈里面。递归完后一旦发现 \(dfn_u=low_u\) 就说明 \(u\) 无法离开以其为根的子树。此时一直弹栈直至弹出点 \(u\)，弹出的这些点就构成了一个强连通分量。

考虑如何求出 \(low_u\)，枚举 \(u\) 的每条出边 \((u,v)\)：

• 点 \(v\) 未遍历过，先递归处理该点，这样 \((u,v)\) 就成了树边，令 \(low_u\gets\min\{low_u,low_v\}\)。
• 点 \(v\) 已遍历过：
  • 点 \(v\) 处于一个已找出的强连通分量中，显然它并不能帮我们走出去，直接跳过。
  • 点 \(v\) 处于未找出的强连通分量中，这样 \((u,v)\) 就成了非树边，同样令 \(low_u\gets\min\{low_u,low_v\}\)。需要注意的是，\(v\) 一定能走到两点的 LCA 处，从而一定能走到 \(u\)。

但存在一个问题，\(low\) 有时会不能更新完全，例如下图。

按照 \(1\to 2\to 3\) 的顺序走，假设先遍历了绿色边，再遍历了红色边，可以发现原因是 \(low_2\) 没有更新完全时就去递归处理了 \(3\) 号点，进而导致 \(low_3\) 也不能更新完全。

这个问题显然是不能避免的，所幸这并不会影响 \(dfn_{low_u}\) 与 \(dfn_u\) 的相对大小。

割点

可以发现无向图不存在横叉边，返祖边由树边和前向边组成。

随便钦定一个根结点，如果存在两棵及以上的子树说明它是割点。

\(dfn\) 定义不变，\(low\) 的定义改成最多经过一条非树边或反向经过一条树边所能到达的最小时间戳。

如果存在边 \((u,v)\) 其中 \(u\) 是 \(v\) 的父亲满足 \(dfn_u=low_v\) 则说明以 \(v\) 为根的子树中的点如果不通过 \(u\) 就与外界不连通了，即 \(u\) 为一个割点。

需要注意的是，删除一个点的同时会删掉以其为端点的所有边，所以 \(low\) 必须按照定义来，如果和强连通分量一样可能会导致中途经过割点。

割边

\(low\) 的定义和割点稍有不同，不能反向经过树边（当然割点你也可以这么写）。

非树边不可能是割边。如果树边 \((u,v)\) 其中 \(u\) 是 \(v\) 的父亲满足 \(low_u>dfn_u\) 则说明以 \(v\) 为根的子树中的点如果不通过 \((v,u)\) 就与外界不连通了。

需要注意的是反向经过一条树边的处理，当出现重边时需要特判一下。

点双连通分量

每次删除割点，分成若干个不连通的子图，然后将割点重新加入每个子图。如果找不到割点就说明已经是点双连通分量了。

当然肯定不用直接这么写，在搜索过程中用栈维护即可。

边双连通分量

找出所有的割边标记为不能经过，剩下的连通块就是所有的边双连通分量。

圆方树

原图中每个点双都对应一个方点，每个点都对应一个圆点，每个方点向其点双中的点对应的圆点连边。

形态就是若干个菊花图通过割点连在一起。