浙大计算机研究生复试上机考试

复试上机考试"/>

浙大计算机研究生复试上机考试

文章目录

• 并查集知识
• 畅通工程
• • 实现代码
  • 样例运行结果

并查集知识

畅通工程

题目原地址

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

输入样例：

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

输出样例

1
0
2
998

实现代码

#include<stdio.h>
#define N 1010
int father[N];int Find(int x) {if(x != father[x]) {father[x] = Find(father[x]);}return father[x];
}void Union(int x, int y) {int a = Find(x);int b = Find(y);if(a != b) {father[a] = b;}
}int main() {while(1) {// n为城镇数, m为道路数int n, m;int ans = 0;scanf("%d", &n);if(n == 0) {break;}scanf("%d", &m);int i;for(i = 1; i <= n; i++) {father[i] = i;}int x, y;for(i = 0; i < m; i++) {scanf("%d %d", &x, &y);Union(x, y);}for(i = 1; i <= n; i++) {if(i == Find(i)) {ans++;}}printf("%d\n", ans - 1);}return 0;
}

样例运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！