警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「算法」Tarjan割点

简介

如果在一张无向图上删除它和它的所有边使图的连通性改变,那么这个点就这张无向图的割点。

概念

强连通分量不同,割点只会在无向图中出现。因为DFS树的特性,这棵树上只会有两种边:树边和反向边。

如下面这张图:

\(1\)点对它进行DFS,可以得到以下的DFS树(这个例子貌似有点极端):

还是一样,定义dfn[i]low[i]

dfn[i]代表第\(i\)个点的DFS序low[i]代表第\(i\)个点及其子树上的某个点通过一条横叉边或返祖边能到达的DFS序最小的点的DFS序。

显然无向图的DFS树中不可能存在所谓的横叉边,因为如果存在的话那么这条边也会变成树边。

流程

现在假设DFS从一个点\(u\),沿着某条边搜到了某个点\(v\),那么会有以下情况:

  1. \(u\)沿着树边到了\(v\):先dfs(v)求出low[v]\(low[u]=\min(low[u],low[v])\)
  2. \(u\)沿着反向边到了\(v\)\(low[u]=\min(low[u],dfn[v])\)

既然每棵子树已经完全独立了,那么一个点\(u\)是不是割点就很好定义了:

  • 如果\(u\)是根并且有至少两个儿子,那么断掉根各个子树就会分成几个不同的连通块,所以这个点是割点。
  • 如果\(u\)不是根且搜到的点\(v\)满足\(low[v]\ge dfn[u]\),那么断掉\(u\)\(v\)就无法到达low[i],所以这个点是割点。

结束了?结束了。

代码

该代码用于Accepted洛谷 P3388 - 【模板】割点(割顶)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

const int N = 100005, M = 200005;

struct Edge {
int to, next;
} e[M];

int head[N];

int cut_count, edge_count, dfn_index;
int n, m, dfn[N], low[N], par[N];

bool cut[N];

void tarjan(int cur) {
dfn[cur] = low[cur] = ++dfn_index;
int cnt = 0;
for (int i = head[cur]; i; i = e[i].next) {
int nxt = e[i].to;
if (nxt == par[cur]) continue;
if (!dfn[nxt]) {
cnt++;
par[nxt] = cur;
tarjan(nxt);
low[cur] = min(low[cur], low[nxt]);
if (par[cur] && low[nxt] >= dfn[cur]) {
cut_count += !cut[cur];
cut[cur] = 1;
}
} else {
low[cur] = min(low[cur], dfn[nxt]);
}
}
if (!par[cur] && cnt >= 2) {
cut_count += !cut[cur];
cut[cur] = 1;
}
}

void addEdge(int u, int v) {
e[++edge_count] = (Edge){v, head[u]};
head[u] = edge_count;
}

int u, v;

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
printf("%d\n", cut_count);
for (int i = 1; i <= n; i++) {
if (cut[i]) {
printf("%d ", i);
}
}
}