【算法模板】图论：Tarjan算法求割边割点

概念

割边（Bridge 或 Cut Edge）

定义：

• 在一个无向连通图中，如果删除某条边后，图不再连通（即恣意两点之间不能相互到达），则称该边为割边。割边也被称为桥，由于它像桥梁一样连接着图的两部分，一旦移除，这两部分就被隔断了。
  

特性：

• 割边只存在于无向连通图中。
  
• 删除割边会导致图的连通分量数目增加。
  
• 割边是图中的一个“薄弱环节”，对于图的连通性有重要影响。
  

边双连通分量（Edge Biconnected Component）

• 定义：
  
  
  
  • 一个无向图的边双连通分量是一个极大连通子图，删除恣意一条边后，图仍然连通。
    
  • 类似于点双连通分量，边双连通分量中的恣意两个节点之间都有两条不相交的边（即，如果删除一条边，仍然可以保持连通）。
    
  
  
• 性质：
  
  
  
  • 边双连通分量的每个分量都是连通的。
    
  • 边双连通分量可用于分析图中冗余的边以及提高图的可靠性。
    
  
  

割点（Articulation Point 或 Cut Vertex）

定义：

• 在一个无向连通图中，如果删除了某个顶点后，图不再连通（即恣意两点之间不能相互到达），则称该顶点为割点。割点也被称为关节点，由于它像关节一样连接着图的差别部分，一旦移除，这些部分就被分开了。
  

特性：

• 割点同样只存在于无向连通图中。
  
• 删除割点会导致图的连通分量数目增加或减少（详细取决于割点的位置和图的布局）。
  
• 割点是图中的一个重要节点，对于维护图的连通性至关重要。
  

点双连通分量（Vertex Biconnected Component）

• 定义：
  
  
  
  • 一个无向图的点双连通分量是一个极大连通子图，删除恣意一个节点后，图仍然连通。
    
  • 换句话说，点双连通分量中的恣意两个节点之间都有两条不相交的路径（即，如果删除一个节点，仍然可以保持连通）。
    
  
  
• 性质：
  
  
  
  • 点双连通分量的每个分量都是连通的。
    
  • 点双连通分量可用来检测图中的割点（即删除后会增加连通分量的节点）。
    
  
  

割点与割边的关系

• 存在割点时必有割边：如果一个节点是割点，那么至少存在一条通过该节点的割边。删除割点会导致图分裂为多个部分，每个部分之间至少存在一条割边。
  
• 割边连接的节点可能是割点：割边的两个端点节点至少有一个可能是割点。特别是在边的两个端点是差别的双连通分量时，这两个节点通常是割点。
  
• 独立的关系：固然割点和割边精密相关，但它们也可以独立存在。一个图可以有割点而没有割边，大概有割边而没有割点。比方，星型图的中心节点是割点，但星型图的每条边都是割边。
  

Tarjan算法

算法头脑

• DFS 访问顺序： 每个节点都有一个 dfn 值，表现节点在 DFS 中被访问的时间戳（第几个被访问）。同时，尚有一个 low 值，表现节点能通过回边或子节点到达的最早访问的节点的时间戳。
  
• 割点判断：
  
  
  
  • 对于根节点，如果它有两个或两个以上的子树，则它是割点。
    
  • 对于非根节点，如果某个子节点的 low 值不小于该节点的 dfn 值，则该节点是割点。
    
  
  
• 割边判断： 如果某个节点 u 和它的子节点 v 之间的边满足 low[v] > dfn，则边 (u, v) 是割边。
  

算法步骤

• 初始化 dfn 和 low 数组，初始值为 -1，表现未被访问。初始化一个时间戳变量 time 为 0。
  
• 使用 DFS 遍历图，对于每个未被访问的节点调用 DFS 函数。
  
• 在 DFS 函数中：
  
  
  
  • 设置当前节点的 dfn 和 low 值为当前时间戳，并将时间戳加 1。
    
  • 对于每个邻接节点，如果该邻接节点未被访问，递归调用 DFS 函数，更新当前节点的 low 值。
    
  • 如果邻接节点已被访问且不是父节点，更新当前节点的 low 值为邻接节点的 dfn 值。
    
  • 在返回时，根据 low 值判断是否是割点或割边。
    
  
  
• 记载所有割点和割边。
  

算法模板

1. // 求解割点的函数
2. vector<int> findCutPoints(const vector<vector<int>> &graph) {
3.     int n = graph.size();
4.     vector<int> cutPoints; // 存储割点
5.     vector<int> dfn(n, -1), low(n), parent(n, -1); // 初始化 dfn, low, parent 数组
6.     vector<bool> visited(n, false); // 记录节点是否已被访问
7.     int time = 0; // 时间戳
9.     // DFS 函数
10.     function<void(int)> dfs = [&](int u) {
11.         visited[u] = true; // 标记节点 u 为已访问
12.         dfn[u] = low[u] = time++; // 设置 dfn 和 low 值
13.         int childCount = 0; // 子节点数量
14.         bool isCutPoint = false; // 是否为割点
16.         // 遍历邻接节点
17.         for (int v : graph[u]) {
18.             if (!visited[v]) { // 如果 v 未被访问
19.                 parent[v] = u; // 设置 v 的父节点为 u
20.                 dfs(v); // 递归调用 DFS
21.                 childCount++; // 增加子节点数量
23.                 // 更新 low[u]
24.                 low[u] = min(low[u], low[v]);
26.                 // 判断是否为割点
27.                 if (parent[u] == -1 && childCount > 1) { // 根节点且有两个以上子树
28.                     isCutPoint = true;
29.                 }
30.                 if (parent[u] != -1 && low[v] >= dfn[u]) { // 非根节点且满足条件
31.                     isCutPoint = true;
32.                 }
33.             } else if (v != parent[u]) { // 如果 v 已被访问且不是父节点
34.                 low[u] = min(low[u], dfn[v]); // 更新 low[u]
35.             }
36.         }
38.         // 如果是割点，加入结果
39.         if (isCutPoint) {
40.             cutPoints.push_back(u);
41.         }
42.     };
44.     // 遍历每个节点，进行 DFS
45.     for (int i = 0; i < n; ++i) {
46.         if (!visited[i]) {
47.             dfs(i);
48.         }
49.     }
51.     return cutPoints; // 返回割点列表
52. }
54. // 求解割边的函数
55. vector<pair<int, int>> findBridges(const vector<vector<int>> &graph) {
56.     int n = graph.size();
57.     vector<pair<int, int>> bridges; // 存储割边
58.     vector<int> dfn(n, -1), low(n), parent(n, -1); // 初始化 dfn, low, parent 数组
59.     vector<bool> visited(n, false); // 记录节点是否已被访问
60.     int time = 0; // 时间戳
62.     // DFS 函数
63.     function<void(int)> dfs = [&](int u) {
64.         visited[u] = true; // 标记节点 u 为已访问
65.         dfn[u] = low[u] = time++; // 设置 dfn 和 low 值
67.         // 遍历邻接节点
68.         for (int v : graph[u]) {
69.             if (!visited[v]) { // 如果 v 未被访问
70.                 parent[v] = u; // 设置 v 的父节点为 u
71.                 dfs(v); // 递归调用 DFS
73.                 // 更新 low[u]
74.                 low[u] = min(low[u], low[v]);
76.                 // 判断是否为割边
77.                 if (low[v] > dfn[u]) {
78.                     bridges.push_back({u, v}); // 记录割边
79.                 }
80.             } else if (v != parent[u]) { // 如果 v 已被访问且不是父节点
81.                 low[u] = min(low[u], dfn[v]); // 更新 low[u]
82.             }
83.         }
84.     };
86.     // 遍历每个节点，进行 DFS
87.     for (int i = 0; i < n; ++i) {
88.         if (!visited[i]) {
89.             dfs(i);
90.         }
91.     }
93.     return bridges; // 返回割边列表
94. }

复制代码

例题

P3388 【模板】割点（割顶）
给出一个 n 个点，m 条边的无向图，求图的割点。

1. #include <bits/stdc++.h>
2. using namespace std;
3. vector<int> findCutPoints(const vector<vector<int>> &graph);
4. signed main() {
5.     int n,m;
6.     cin>>n>>m;
7.     vector<vector<int>> G(n+1);
8.     while(m--){
9.         int u,v;
10.         cin>>u>>v;
11.         G[u].push_back(v);
12.         G[v].push_back(u);
13.     }
14.     vector<int> CutPoints=findCutPoints(G);
15.     cout<<CutPoints.size()<<endl;
16.     sort(CutPoints.begin(),CutPoints.end());
17.     for(int p:CutPoints)cout<<p<<' ';
18.     return 0;
19. }

复制代码

P1656 炸铁路
将军uim需要选择一条铁路进行炸毁，以使得B国的物流体系瘫痪，导致至少存在两个城市无法通过铁路相互到达。要选择的铁路被称为“关键铁路”。

1. #include <bits/stdc++.h>
2. using namespace std;
3. vector<pair<int, int>> findBridges(const vector<vector<int>> &graph);
4. signed main() {
5.     int n,m;
6.     cin>>n>>m;
7.     vector<vector<int>> G(n+1);
8.     while(m--){
9.         int u,v;
10.         cin>>u>>v;
11.         G[u].push_back(v);
12.         G[v].push_back(u);
13.     }
14.     vector<pair<int, int>> Bridges=findBridges(G);
15.     for(auto&[x,y]:Bridges)if(x>y)swap(x,y);
16.     sort(Bridges.begin(),Bridges.end());
17.     for(auto[x,y]:Bridges)cout<<x<<' '<<y<<endl;
18.     return 0;
19. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。