割点、割边、点双连通分量、边双连通分量
前置知识：
Tarjan算法
SCC缩点
割点
定义
在无向图中，若删除某个顶点 u 后，图的连通分量数量增加，则称 u 为割点。
寻找方法
利用Tarjan的时间戳 dfn（记录节点首次被访问的顺序）和追溯值 low（记录节点或其子孙能通过非树边追溯到的最早时间戳）判断：
- 对于根节点（DFS 树的起点）：若其有至少 2 个子树，则为割点（删除根后子树间断开）。
- 对于非根节点 u：若存在子节点 v 满足 $(low[v] \geq dfn[u])$，则 u 为割点。
（v 及其子孙无法绕过 u 到达更早访问的节点，删除 u 后 v 所在子树与其他部分断开）
视频讲解
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
vector<int> g[N];
vector<int> ans;
int dfn[N],low[N],tstramp,root;
void tarjan(int x)
{
dfn[x] = low[x] = ++tstramp;
int child = 0;
for(auto v : g[x])
{
if(!dfn[v])
{
tarjan(v);
low[x] = min(low[x],low[v]);
if(low[v]>=dfn[x])
{
child++;
if(x!=root or child>1)//特判root节点
ans.push_back(x);
}
}
else low[x] = min(low[x],dfn[v]);
}
}
|
割边
定义
在无向图中，若删除某条边 $(u, v)$ 后，图的连通分量数量增加，则称该边为割边（或桥）
寻找方法
对于边 $(u, v)$（假设 u 是 v 在树中的父节点），若 $(low[v] > dfn[u])$，则 $(u, v)$ 是割边。
（v 及其子孙无法通过非树边追溯到 u 或更早节点，删除该边后 v 所在子树与其他部分断开）
与割点的区别
割边的判断更严格：$low[v] > dfn[u]$（等号不成立，若 $low[v] = dfn[u]$，说明存在其他路径连接 v 和 u，边非割边）
视频讲解
实现
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
|
vector<pair<int,int>> edges;
vector<int> idx[N];
vector<pair<int,int>> ans;
void add(int u,int v)
{
edges.push_back({u,v});
idx[u].push_back(edges.size()-1);
}
int dfn[N],low[N],tstramp;
void tarjan(int x,int ls)
{
dfn[x] = low[x] = ++tstramp;
for(auto t : idx[x])
{
int v = edges[t].second;
if(!dfn[v])
{
tarjan(v,t);
low[x] = min(low[x],low[v]);
if(low[v] > dfn[x]) ans.push_back({x,v});
}
else if(t!=(ls^1))
low[x] = min(low[x],dfn[v]);
}
}
|
点双连通分量（vDCC缩点）
定义
-
给定一个无向连通图 $G=(V,E)$。若去掉图中的任意 一个 顶点（及其所有关联边）都不会使图不连通，则称 $G$ 是 点双连通图。
-
点双连通分量是在图中最大的点双连通子图。换言之，它是一棵包含若干顶点和边的子图，对任一顶点的删除都不破坏其连通性，而且不能再向外扩展而保持此性质。
判定与求解
常用 Tarjan 来判定割点并划分
视频讲解
实现
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
68
|
int dfn[N],low[N],tstramp,cnt,root,idx[N];
bool cut[N];
stack<int> st;
vector<int> dcc[N];
vector<int> g[N];
void tarjan(int x)
{
dfn[x] = low[x] = ++tstramp;
st.push(x);
if(!g[x].size())
{
dcc[++cnt].push_back(x);
return;
}
int child = 0;
for(auto v : g[x])
{
if(!dfn[v])
{
tarjan(v);
low[x] = min(low[x],low[v]);
if(low[v]>=dfn[x])
{
child++;
if(x!=root or child>2)
cut[x] = true;
cnt++;
int y;
do{
y = st.top();
dcc[cnt].push_back(y);
st.pop();
}while(y != v);
dcc[cnt].push_back(x);
}
}
else low[x] = min(low[x],dfn[v]);
}
}
void solve()
{
int n,m;cin >> n >> m;
for(int i=1;i<=m;i++)
{
int u,v;cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) root = i,tarjan(i);
int num = cnt;
//vDCC缩点
for(int i=1;i<=n;i++)
if(cut[i]) idx[i] = ++num;
for (int i = 1; i <= cnt; i++)
{
for (auto x : dcc[i])
{
if (cut[x])
{
ng[i].push_back(idx[x]),
ng[idx[x]].push_back(i);
}
else idx[x] = i;
}
}
}
|
边双连通分量（eDCC缩点）
定义
判定与求解
边双连通分量的划分依赖于 桥（bridge）的发现：
-
在 DFS 中同样维护 dfn[u] 和 low[u]。若存在一条树边 $(u,v)$ 满足 low[v] > dfn[u]，则该边是 桥，去掉它会增加连通分支数。
-
将图中所有桥删除后，剩余的连通块即为各个 eDCC。
视频讲解
实现
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
68
|
vector<pair<int,int>> edges;
vector<int> idx[N];
int dcc[N]; // 每个点所属的边双连通分量编号
bool cut[N * 2]; // 标记某条边是否是桥（true 表示桥）
int dfn[N], low[N], tstramp, cnt;
stack<int> st;
// 添加边 (无向图存两条边)
void add(int u,int v)
{
edges.push_back({u,v});
idx[u].push_back((int)edges.size()-1);
}
void tarjan(int x,int ls)
{
dfn[x] = low[x] = ++tstramp;
st.push(x);
for(auto t : idx[x])
{
int v = edges[t].second;
if(!dfn[v])
{
tarjan(v,t);
low[x] = min(low[x],low[v]);
if(low[v] > dfn[x]) cut[t] = cut[t ^ 1] = true;
}
else if(t != (ls ^ 1))
low[x] = min(low[x], dfn[v]);
}
if(dfn[x] == low[x])
{
cnt++;
int y;
do{
y = st.top();
st.pop();
dcc[y] = cnt;
}while(y!=x)
}
}
int in[N];
void solve()
{
int n,m; cin >> n >> m;
for(int i=1; i<=m; i++)
{
int u,v; cin >> u >> v;
add(u,v); add(v,u);
}
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i, 0);
// 缩点后统计入度（示例）
for(int i=0; i<(int)edges.size(); i++)
{
if(cut[i])
{
int u = edges[i].first;
int v = edges[i].second;
int uid = dcc[u];
int vid = dcc[v];
if(uid != vid)
in[vid]++; // 桥连通不同的DCC，更新入度
}
}
}
|
示例
假设如下无向图：
1
2
3
4
5
6
7
|
A
/ \
B C
\ / \
D E
\
F
|
-
割点：$D\text、C$
-
vDCC：
-
子图 ${A, B, C, D}$（一个二连通块，有环 $A–B–D–C–A$）
-
子图 $(C, E)$（只有一条边，退化的二连通块）
-
子图 $(E, F)$
-
割边： $(C,E)\text、(E,F)$
-
eDCC：
-
主环 {A, B, C, D}
-
边 $(C,E)$ 单独一块
-
边 $(E,F)$ 单独一块
例题
P3388 【模板】割点（割顶）
P8435 【模板】点双连通分量
P8436 【模板】边双连通分量
P3854 [TJOI2008] 通讯网破坏
