浙大计算机研究生复试上机考试-2005年畅通工程（考察并查集）

并查集知识

畅通工程

题目原地址

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

输入样例：

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
1
2
3
4
5
6
7
8
9
10
11
12

输出样例

1
0
2
998
1
2
3
4

实现代码

#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

样例运行结果

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