本课时有配套视频讲解，购买后即可观看（永久有效）

图及图的连通性

一、课上练习

编程练习

（暂无）

二、知识总结

✨ 核心思想

图的连通性是图论中的基础概念。对于无向图，连通性指的是任意两点之间是否存在路径；对于有向图，则分为强连通和弱连通。在竞赛中，常考的连通性问题包括：求连通分量、判断连通性、找割点（关节点）和桥（割边）等。理解图的连通性是解决更复杂图论问题的基石。

✨ 算法原理

基本概念：

连通图：无向图中，任意两个顶点之间都有路径相连
连通分量：无向图中的极大连通子图
强连通图：有向图中，任意两个顶点之间都有互相可达的路径
桥（割边）：删除该边后图不再连通的边
割点（关节点）：删除该点及其关联边后图不再连通的点

求连通分量： 使用 DFS 或 BFS 遍历图，每次从未访问的点出发，能到达的所有点构成一个连通分量。

Tarjan 算法求割点和桥：

Tarjan 算法基于 DFS 树，引入两个关键数组：

dfn[u]：节点 u 的 DFS 序（第几个被访问到）
low[u]：节点 u 能通过回边到达的最小 dfn 值

割点判定条件：

若 u 是 DFS 树的根节点：u 是割点当且仅当 u 有两个或以上的子树
若 u 不是根节点：u 是割点当且仅当存在子节点 v 使得 low[v] >= dfn[u]

桥的判定条件：

边 (u, v) 是桥当且仅当 low[v] > dfn[u]（注意是严格大于）

✨ 代码实现

1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<int> adj[MAXN]; // 邻接表
7bool visited[MAXN];
8int comp[MAXN]; // 每个节点所属的连通分量编号
9int cnt; // 连通分量计数
10
11// DFS遍历，标记同一连通分量
12void dfs(int u, int id) {
13    visited[u] = true;
14    comp[u] = id;
15    for (int v : adj[u]) {
16        if (!visited[v]) {
17            dfs(v, id);
18        }
19    }
20}
21
22int main() {
23    int n, m;
24    cin >> n >> m;
25
26    // 读入无向图
27    for (int i = 0; i < m; i++) {
28        int u, v;
29        cin >> u >> v;
30        adj[u].push_back(v);
31        adj[v].push_back(u);
32    }
33
34    // 求所有连通分量
35    cnt = 0;
36    for (int i = 1; i <= n; i++) {
37        if (!visited[i]) {
38            cnt++;
39            dfs(i, cnt);
40        }
41    }
42
43    cout << "连通分量个数：" << cnt << endl;
44    return 0;
45}

1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<int> adj[MAXN];
7int dfn[MAXN], low[MAXN]; // DFS序和能到达的最小DFS序
8int timer_cnt = 0; // 时间戳计数器
9bool isCut[MAXN]; // 标记割点
10int n, m;
11
12// 存储桥
13vector<pair<int,int>> bridges;
14
15// Tarjan DFS
16// u: 当前节点, fa: 父节点（用于避免走回父边）
17void tarjan(int u, int fa) {
18    dfn[u] = low[u] = ++timer_cnt;
19    int childCount = 0; // 子树数量（仅用于判断根节点）
20
21    for (int v : adj[u]) {
22        if (!dfn[v]) {
23            // v尚未访问，是树边
24            childCount++;
25            tarjan(v, u);
26
27            // 用子节点的low值更新当前节点
28            low[u] = min(low[u], low[v]);
29
30            // 判断割点
31            // 非根节点：子节点无法绕过u到达u的祖先
32            if (fa != -1 && low[v] >= dfn[u]) {
33                isCut[u] = true;
34            }
35
36            // 判断桥：子节点完全无法到达u及u的祖先
37            if (low[v] > dfn[u]) {
38                bridges.push_back({u, v});
39            }
40        } else if (v != fa) {
41            // v已访问且不是父节点，是回边
42            low[u] = min(low[u], dfn[v]);
43        }
44    }
45
46    // 根节点：有两个以上子树则为割点
47    if (fa == -1 && childCount >= 2) {
48        isCut[u] = true;
49    }
50}
51
52int main() {
53    cin >> n >> m;
54    for (int i = 0; i < m; i++) {
55        int u, v;
56        cin >> u >> v;
57        adj[u].push_back(v);
58        adj[v].push_back(u);
59    }
60
61    // 对每个连通分量运行Tarjan
62    for (int i = 1; i <= n; i++) {
63        if (!dfn[i]) {
64            tarjan(i, -1);
65        }
66    }
67
68    // 输出割点
69    cout << "割点：";
70    for (int i = 1; i <= n; i++) {
71        if (isCut[i]) cout << i << " ";
72    }
73    cout << endl;
74
75    // 输出桥
76    cout << "桥：" << endl;
77    for (auto& e : bridges) {
78        cout << e.first << " - " << e.second << endl;
79    }
80
81    return 0;
82}

✨ 执行示例

以如下无向图为例（7 个节点，7 条边）：

1 --- 2 --- 3
|         / |
4    5 --- 6
     |
     7

边：(1,2), (1,4), (2,3), (3,5), (3,6), (5,6), (5,7)

DFS 过程（从节点 1 开始）：

1访问 1: dfn[1]=1, low[1]=1
2  → 访问 2: dfn[2]=2, low[2]=2
3    → 访问 3: dfn[3]=3, low[3]=3
4      → 访问 5: dfn[5]=4, low[5]=4
5        → 访问 6: dfn[6]=5, low[6]=5
6          → 6的邻居3已访问(回边)，low[6]=min(5,3)=3
7        low[5]=min(4,3)=3
8        → 访问 7: dfn[7]=6, low[7]=6
9        low[5]不变，仍为3
10      low[3]=min(3,3)=3
11    low[2]=min(2,3)=2
12  → 访问 4: dfn[4]=7, low[4]=7
13  low[1]=min(1,2)=1, 但low[4]=7>=dfn[1]=1
14
15割点判断：
16  节点1是根，有两个子树(2和4)，是割点
17  节点3: low[5]=3>=dfn[3]=3，是割点
18  节点5: low[7]=6>=dfn[5]=4，是割点
19
20桥判断：
21  (1,4): low[4]=7>dfn[1]=1，是桥
22  (5,7): low[7]=6>dfn[5]=4，是桥

✨ 解题步骤详解

建图：根据题意建立邻接表（注意有向/无向）
选择算法：
- 只需求连通分量 → DFS/BFS 即可
- 需要割点或桥 → Tarjan 算法
- 有向图强连通分量 → Tarjan 或 Kosaraju 算法
初始化：清空 dfn、low 数组，设置计数器
处理非连通图：对每个未访问的节点调用 DFS
根据 dfn 和 low 判断：割点用 >=，桥用 >

✨ 常见错误

重边处理不当：如果图有重边，不能简单地用 v != fa 跳过，需要用边的编号来区分
根节点割点判断遗漏：根节点需要单独判断子树数量
混淆割点和桥的条件：割点是 >=，桥是 >，容易搞混
忘记处理非连通图：需要对所有未访问节点都执行 Tarjan
low 数组更新错误：回边只更新到 dfn[v]，不应更新到 low[v]
有向图和无向图的处理方式不同：无向图需要避免走回父边，有向图不需要

✨ 算法评价

指标	值
DFS 求连通分量	O(V + E) 时间，O(V) 空间
Tarjan 求割点/桥	O(V + E) 时间，O(V) 空间
BFS 求连通分量	O(V + E) 时间，O(V) 空间

图的连通性分析是许多高级图论算法的基础，如双连通分量分解、强连通缩点等。掌握 Tarjan 算法是学习这些高级内容的前提。