AcWing 3719. 畅通工程
原题链接
简单
作者:
Timmmm
,
2024-01-21 13:51:19
,
所有人可见
,
阅读 45
#include<bits/stdc++.h> // 万能头
#define MAXN 10001 // 数组的最大范围
int fa[MAXN], Rank[MAXN];// 每个节点的根节点和每个节点的秩
using namespace std;
// 初始化每个节点的根节点(自己)和每个节点的秩(自己即1)
inline void init(int n) {
for (int i = 1; i <= n; i ++ ) {
fa[i] = i;
Rank[i] = 1;
}
}
// 找出某点的根节点
int find(int x)
{
// 使用路径压缩找到所有点的父节点
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
// 合并两个节点为一个树
inline void merge(int i, int j) {
int x = find(i), y = find(j); // 找到i和j的根节点
if(Rank[x] <= Rank[y]) // 判断,如果x树的深度小于等于y树的深度
fa[x] = y; // 则将x树合并到y树下
else
fa[y] = x;
if(Rank[x] == Rank[y] && x != y) { // 如果x树和y树的深度一样
Rank[y] ++; // 合并后y树深度需要加一
}
}
int main() {
int N, M, x, y, ans = 0;
cin >> N >> M; // 输入N个城镇和M条道路
init(N); // 初始化N个点
// 循环输入M条道路
for (int i = 0; i < M; i ++ ) {
cin >> x >> y; // 输入已有道路的两个城镇
merge(x, y); // 合并
}
// 循环判断所有节点,如果根是自己,说明需要一条路,最后需要减1(n个点连接需要n-1条路)
for (int i = 1; i <= N; i ++) {
if(find(i) == i)
ans ++;
}
cout << ans - 1;
return 0;
}