HDU 1232 畅通工程

这个题目也是典型的最小生成树算法的利用，不同于其他的题目就在于其它要求的是要添加的边的最少数目，使得任意两
点都有联系，利用并查集算法，在题目已经给出的map基础上，统计两棵树相并的次数，即使要添加的路径的最少数目。

1 #include<stdio.h>
2 #include<stdlib.h>
3
4 int father[1001], tot;//father[i] 记录 i 的 BOSS ！
5 //tot 统计最初至少需要添加的路径数目！
6
7 int find(int x)
8 {//找到 x 的 BOSS ！
9     int r = x;
10     while (r != father[r]) r = father[r];
11     return r;//
12 }
13
14 void join(int a, int b)
15 {//将 a 和 b 的 BOSS 统一！
16      int fa = find(a), fb = find(b);
17      if (fa != fb)
18      {
19         father[fa] = fb;
20         tot --; // 统一了一次两个阵营的 BOSS ，所以需要添加的路径的数目减一！
21      }
22 }
23
24 int main()
25 {
26     int n, m, x, y;
27     while (scanf("%d", &n), n)
28     {
29           scanf("%d", &m);
30           tot = n-1; // 初始化 tot 等于 n 个点联通所需要的最少边的数目！
31           father[n+1];
32           for (int i=1; i<=n; i++)father[i] = i;//初始化自己是自己的 BOSS ！
33
34           for (int i=1; i<=m; i++)
35           {
36               scanf("%d %d",&x, &y);
37               join(x, y);
38           }
39           printf("%d\n",tot); //输出在已有基础上还需要的边的数目！
40     }
41     return 0;
42 }
43

补充：软件开发 , C语言 ,