✏️ 纠错
#include <cstdio>
using namespace std;
const int N = 1e5 + 5; // 最大节点数（1e5+5 避免越界）
int n, m; // n：节点数，m：边数
int f[N]; // 并查集的父节点数组（f[u]表示 u 的父节点）
int ans; // 连通分量数量
// 查找 u 的根节点（路径压缩优化）
int getf(int u) {
// 如果 f[u]为 0，说明 u 是根节点；否则递归查找父节点并压缩路径
return f[u] ? f[u] = getf(f[u]) : u;
}
int main() {
scanf("%d%d", &n, &m);
// 处理每条边，合并两个节点所在的集合
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
// 查找 u 和 v 的根节点
int root_u = getf(u);
int root_v = getf(v);
// 若根节点不同，则合并（将 root_u 的父节点设为 root_v）
if (root_u != root_v) {
f[root_u] = root_v;
}
}
// 统计连通分量数量（根节点的数量）
for (int i = 1; i <= n; i++) {
// 若 i 是根节点（getf(i) == i），则分量数+1
if (getf(i) == i) {
ans++;
}
}
// 最少需要添加的边数 = 分量数 - 1
printf("%d\n", ans - 1);
return 0;
}
第 152 题 / 共 155 题
题目描述
给定一张包含 n 个结点与 m 条边的无向图，结点依次以 1,2,…,n 编号，第 i 条边（1≤i≤m）连接结点 ui 与结点 vi。如果从一个结点经过若干条边可以到达另一个结点，则称这两个结点是连通的。
你需要向图中加入若干条边，使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。
注意给出的图中可能包含重边与自环。
输入格式
第一行，两个正整数 n,m，表示图的点数与边数。
接下来 m 行，每行两个正整数 ui,vi，表示图中一条连接结点 ui 与结点 vi 的边。
输出格式
输出一行，一个整数，表示使得图中任意两个结点连通所需加入的边的最少数量。
输入输出样例
输入 #1
4 4 1 2 2 3 3 1 1 4
输出 #1
0
输入 #2
6 4 1 2 2 3 3 1 6 5
输出 #2
2
说明/提示
对于 40% 的测试点，保证 1≤n≤100，1≤m≤100。
对于所有测试点，保证 1≤n≤105，1≤m≤105。
你真棒！
📝 题目解析
问题核心：求使无向图连通所需添加的最少边数。
关键观察：
一个连通图的「连通分量」（彼此独立的子图）数量为k时，最少需要k-1条边即可将所有分量连接成一个连通图（例如：3个分量需2条边）。
解决方案：使用「并查集」（Union-Find）计算连通分量数量，最终答案为分量数- 1。
代码注释
#include <algorithm>#include <cstdio>
using namespace std;
const int N = 1e5 + 5; // 最大节点数（1e5+5 避免越界）
int n, m; // n：节点数，m：边数
int f[N]; // 并查集的父节点数组（f[u]表示 u 的父节点）
int ans; // 连通分量数量
// 查找 u 的根节点（路径压缩优化）
int getf(int u) {
// 如果 f[u]为 0，说明 u 是根节点；否则递归查找父节点并压缩路径
return f[u] ? f[u] = getf(f[u]) : u;
}
int main() {
scanf("%d%d", &n, &m);
// 处理每条边，合并两个节点所在的集合
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
// 查找 u 和 v 的根节点
int root_u = getf(u);
int root_v = getf(v);
// 若根节点不同，则合并（将 root_u 的父节点设为 root_v）
if (root_u != root_v) {
f[root_u] = root_v;
}
}
// 统计连通分量数量（根节点的数量）
for (int i = 1; i <= n; i++) {
// 若 i 是根节点（getf(i) == i），则分量数+1
if (getf(i) == i) {
ans++;
}
}
// 最少需要添加的边数 = 分量数 - 1
printf("%d\n", ans - 1);
return 0;
}
复杂度分析
时间复杂度：O(n+ma(n))，其中a(n)是并查集的反阿克曼函数（近似常数，可忽略），适用于n,m≤1e5的数据范围。
空间复杂度：O(n)，用于存储并查集的父节点数组。