好的，这是一份关于“连通图”题目的题解，请查阅。

---

连通图 题解

题目分析

题目的核心要求是：给定一张无向图，问最少添加多少条边，可以使整张图连通（任意两点之间都存在路径）。

图可能包含重边和自环。重边和自环对“连通性”没有任何帮助，可以直接忽略。问题等价于：找出图中有多少个连通分量，然后用边将这些连通分量连接起来。

如果我们把每个连通分量看作一个“超级结点”，那么要将 k 个超级结点连接成一棵树，最少需要 k - 1 条边。因此，答案 = 连通分量个数 - 1。

对于 n = 1 的情况，连通分量个数为 1，答案 0，公式依然成立。

解题思路

1. 连通分量计数：遍历所有结点，判断哪些结点属于同一个连通块。可以使用深度优先搜索（DFS）、广度优先搜索（BFS）或并查集实现。
2. 对于每条给出的边 (u, v)，将 u 和 v 所在的集合合并。
3. 最后统计有多少个不同的集合（即连通分量），输出 集合数 - 1。

由于数据范围较大（n, m ≤ 1e5），需要选用时间复杂度接近 O(n + m) 的算法。并查集（Disjoint Set Union）是实现这一类问题最简洁高效的工具。

算法说明：并查集

并查集支持两种操作：

• 查找 (find)：确定一个元素属于哪个集合（通常返回集合的代表元素，即“根”）。
• 合并 (union)：将两个不同的集合合并为一个。

实现中通常采用路径压缩和按秩合并（或简单按大小合并）来使操作接近常数时间。在本题中，直接使用路径压缩就足够高效。

核心步骤

1. 初始化 f 数组，f[i] = i（每个结点自成一个集合）。也可以像参考代码中那样用 0 表示根节点，但 f[i] = i 的形式更直观。
2. 读入每一条边 (u, v)：
   • 找到 u 的根 ru，v 的根 rv。
   • 如果 ru != rv，则令 f[ru] = rv（将两个集合合并）。
3. 遍历 1 ~ n，统计 find(i) == i 的结点个数，即为连通分量个数 cnt。
4. 输出 cnt - 1。

注意：参考代码中 f[getf(u)] = v 的写法在大部分情况下可能正确，但不够严谨。因为 v 不一定是它所在集合的根结点，合并时应当将两个集合的根进行合并，即 f[getf(u)] = getf(v)。这一点在题解代码中进行了修正。

时间复杂度分析

• 初始化并查集：O(n)
• 每条边进行两次 find 和一次合并：O(m · α(n))，其中 α(n) 是反阿克曼函数，可以视为常数。
• 最后统计连通分量：O(n · α(n))。

总体时间复杂度为 O(n + m)，可以在 1 秒内轻松处理 1e5 规模的数据。

参考代码

下面是修正后的并查集实现（加入了路径压缩）：

cpp
复制
1#include <cstdio>
2using namespace std;
3
4const int N = 1e5 + 5;
5int n, m;
6int f[N];
7
8// 查找根结点，同时进行路径压缩
9int find(int x) {
10    if (f[x] != x) f[x] = find(f[x]);
11    return f[x];
12}
13
14int main() {
15    scanf("%d%d", &n, &m);
16    
17    // 初始化：每个结点的父亲指向自己
18    for (int i = 1; i <= n; i++) f[i] = i;
19    
20    for (int i = 1; i <= m; i++) {
21        int u, v;
22        scanf("%d%d", &u, &v);
23        int ru = find(u);
24        int rv = find(v);
25        // 如果不在同一集合，则将它们合并
26        if (ru != rv) f[ru] = rv;
27    }
28    
29    int cnt = 0; // 连通分量个数
30    for (int i = 1; i <= n; i++) {
31        if (find(i) == i) cnt++;
32    }
33    
34    printf("%d\n", cnt - 1);
35    return 0;
36}

代码说明

1. f[x] 记录 x 的父结点，初始化时 f[i] = i 表示每个结点自成一棵树。
2. find(x) 函数递归查找 x 所在集合的根，同时将沿途结点的父结点直接指向根（路径压缩），加快后续查询。
3. 对于每条边 (u, v)，找到它们的根 ru 和 rv。若不同，则令 f[ru] = rv，完成合并。
4. 遍历 1 到 n，如果 find(i) == i，说明 i 是一个集合的根，即找到一个连通分量。
5. 设连通分量数为 cnt，最少需要添加 cnt - 1 条边即可让整张图连通。

总结

本题是一道典型的并查集入门应用题，核心在于将“添加最少边使图连通”转化为“连通分量个数减一”。由于存在重边和自环，在合并时需要忽略已经连通的情况（即两个结点已在同一集合）。掌握并查集后，该题可以直接套用模板解决。