A23806. 连通图
填空题
困难
知识点
题目描述
连通图
题目描述
给定一张包含 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 。
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int f[N];
int ans;
int getf(int 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);
if (getf(u) != getf(v)) f[getf(u)] = v;
}
for (int i = 1; i <= n; i++) ans += getf(i) == i;
printf("%d\n", ans - 1);
return 0;
}
上一题
下一题