割點和橋
相關閲讀：雙連通分量，
割點和橋更嚴謹的定義參見 圖論相關概念。
割點
對於一個無向圖，如果把一個點刪除後這個圖的極大連通分量數增加了，那麼這個點就是這個圖的割點（又稱割頂）。
過程
如果我們嘗試刪除每個點，並且判斷這個圖的連通性，那麼複雜度會特別的高。所以要介紹一個常用的算法：Tarjan。
首先，我們上一個圖：
很容易的看出割點是 2，而且這個圖僅有這一個割點。
首先，我們按照 DFS 序給他打上時間戳（訪問的順序）。
這些信息被我們保存在一個叫做 dfn 的數組中。
還需要另外一個數組 low，用它來存儲不經過其父親能到達的最小的時間戳。
例如 low[2] 的話是 1，low[5] 和 low[6] 是 3。
然後我們開始 DFS，我們判斷某個點是否是割點的根據是：對於某個頂點 \(u\)，如果存在至少一個頂點 \(v\)（\(u\) 的兒子），使得 \(low_v \geq dfn_u\)，即不能回到祖先，那麼 \(u\) 點為割點。
此根據惟獨不適用於搜索的起始點，其需要特殊考慮：若該點不是割點，則其他路徑亦能到達全部結點，因此從起始點只「向下搜了一次」，即在搜索樹內僅有一個子結點。如果在搜索樹內有兩個及以上的兒子，那麼他一定是割點了（設想上圖從 2 開始搜索，搜索樹內應有兩個子結點：3 或 4 及 5 或 6）。如果只有一個兒子，那麼把它刪掉，不會有任何的影響。比如下面這個圖，此處形成了一個環。
我們在訪問 1 的兒子時候，假設先 DFS 到了 2，然後標記用過，然後遞歸往下，來到了 4，4 又來到了 3，當遞歸回溯的時候，會發現 3 已經被訪問過了，所以不是割點。
更新 low 的偽代碼如下：
| 如果 v 是 u 的兒子 low[u] = min(low[u], low[v]);
否則
low[u] = min(low[u], dfn[v]);
|
例題
洛谷 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 | /*
洛谷 P3388 【模板】割点（割顶）
*/
#include <bits/stdc++.h>
using namespace std;
int n, m; // n：点数 m：边数
int dfn[100001], low[100001], inde, res;
// dfn：记录每个点的时间戳
// low：能不经过父亲到达最小的编号，inde：时间戳，res：答案数量
bool vis[100001], flag[100001]; // flag: 答案 vis：标记是否重复
vector<int> edge[100001]; // 存图用的
void Tarjan(int u, int father) { // u 当前点的编号，father 自己爸爸的编号
vis[u] = true; // 标记
low[u] = dfn[u] = ++inde; // 打上时间戳
int child = 0; // 每一个点儿子数量
for (auto v : edge[u]) { // 访问这个点的所有邻居 （C++11）
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] = true;
res++; // 记录答案
}
} else if (v != father)
low[u] =
min(low[u], dfn[v]); // 如果这个点不是自己，更新能到的最小节点编号
}
if (father == u && child >= 2 &&
!flag[u]) { // 主要代码，自己的话需要 2 个儿子才可以
flag[u] = true;
res++; // 记录答案
}
}
int main() {
cin >> n >> m; // 读入数据
for (int i = 1; i <= m; i++) { // 注意点是从 1 开始的
int x, y;
cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
} // 使用 vector 存图
for (int i = 1; i <= n; i++) // 因为 Tarjan 图不一定连通
if (!vis[i]) {
inde = 0; // 时间戳初始为 0
Tarjan(i, i); // 从第 i 个点开始，父亲为自己
}
cout << res << endl;
for (int i = 1; i <= n; i++)
if (flag[i]) cout << i << " "; // 输出结果
return 0;
}
|
割邊
和割點差不多，叫做橋。
對於一個無向圖，如果刪掉一條邊後圖中的連通分量數增加了，則稱這條邊為橋或者割邊。嚴謹來説，就是：假設有連通圖 \(G=\{V,E\}\)，\(e\) 是其中一條邊（即 \(e \in E\)），如果 \(G-e\) 是不連通的，則邊 \(e\) 是圖 \(G\) 的一條割邊（橋）。
比如説，下圖中，
紅色的邊就是割邊。
過程
和割點差不多，只要改一處：\(low_v>dfn_u\) 就可以了，而且不需要考慮根節點的問題。
割邊是和是不是根節點沒關係的，原來我們求割點的時候是指點 \(v\) 是不可能不經過父節點 \(u\) 為回到祖先節點（包括父節點），所以頂點 \(u\) 是割點。如果 \(low_v=dfn_u\) 表示還可以回到父節點，如果頂點 \(v\) 不能回到祖先也沒有另外一條回到父親的路，那麼 \(u-v\) 這條邊就是割邊。
實現
下面代碼實現了求割邊，其中，當 isbridge[x] 為真時，(father[x],x) 為一條割邊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | int low[MAXN], dfn[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];
void tarjan(int u, int fa) {
father[u] = fa;
low[u] = dfn[u] = ++dfs_clock;
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]);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | low = [0] * MAXN; dfn = [0] * MAXN; dfs_clock = 0
isbridge = [False] * MAXN
G = [[0 for i in range(MAXN)] for j in range(MAXN)]
cnt_bridge = 0
father = [0] * MAXN
def tarjan(u, fa):
father[u] = fa
low[u] = dfn[u] = dfs_clock
dfs_clock = dfs_clock + 1
for i in range(0, len(G[u])):
v = G[u][i]
if dfn[v] == False:
tarjan(v, u)
low[u] = min(low[u], low[v])
if low[v] > dfn[u]:
isbridge[v] = True
cnt_bridge = cnt_bridge + 1
elif dfn[v] < dfn[u] and v != fa:
low[u] = min(low[u], dfn[v])
|
練習
Tarjan 算法還有許多用途，常用的例如求強連通分量，縮點，還有求 2-SAT 的用途等。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, sshwy, GavinZhengOI, Planet6174, ouuan, Marcythm, ylxmf2005, 0xis-cn
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用