定义

若对于无向连通图的一个点 $x$，从图中删去这个点和与这个点相连的所有边后，图不再是连通图，则 $x$ 为这个图的割点。

若对于无向连通图的一条边 $e$，从图中删去这条边后，图不再是连通图，则 $e$ 为这个图的割边（桥）。

求解

无向图的搜索树

从任意一个点出发进行 DFS，每个点只能访问一次，所有被访问过的结点和边构成一棵搜索树。

然后就可以将图上的边分为两类，树边和返祖边，返祖边连接了一个点和它的一个祖先。

时间戳 dfn 和追溯值 low

$dfn[x]$ 表示在 DFS 的过程中，$x$ 第一次被访问的顺序。

$low[x]$ 表示 $x$ 和 $x$ 的子树中所有点的时间戳 和 从 $x$ 的子树中的点通过仅一条返祖边可以达到的点的时间戳 的最小值。

更新 $low$ 的方法：

  • 如果 $v$ 是 $u$ 的儿子：$low[u] = min(low[u], low[v])$
  • 否则：$low[u] = min(low[u], dfn[v])$

割点的判定

对于某个点 $u$，如果它的儿子中存在一个点 $v$，使得 $low[v] \ge dfn[u]$，即不能回到祖先，那么 $u$ 就是割点。

对于搜索树的根节点就比较特殊，如果它在搜索树中只有一个儿子，是不能成为割点的，需要特判。

树的叶子节点由于没有儿子，也不能成为割点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void tarjan(int u, int father) {
	int child = 0;
	vis[u] = 1;
	low[u] = dfn[u] = ++inde;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (!vis[v]) {
			child++;
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (father != u && low[v] >= dfn[u] && !flag[u]) {
				flag[u] = 1;
				res++;
			}
		} else if (v != father) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (u == father && child >= 2 && !flag[u]) { // 特判根节点
		flag[u] = 1;
		res++;
	}
}

割边的判定

与割点同理，只需要修改成：$low[v] \gt dfn[u]$ 即可，不需要考虑是否为根节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void tarjan(int u, int fa) {
  father[u] = fa;
  low[u] = dfn[u] = ++inde;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else if (dfn[v] < dfn[u] && v != fa) {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

参考资料