HDU 1232 暢通工程這個(gè)題目也是典型的最小生成樹算法的利用，不同于其他的題目就在于其它要求的是要添加的邊的最少數(shù)目，使得任意兩
點(diǎn)都有聯(lián)系，利用
并查集算法 ，在題目已經(jīng)給出的map基礎(chǔ)上，統(tǒng)計(jì)兩棵樹相并的次數(shù)，即使要添加的路徑的最少數(shù)目。
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 int father[1001], tot;//father[i] 記錄 i 的 BOSS ！
5 //tot 統(tǒng)計(jì)最初至少需要添加的路徑數(shù)目 ！
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 統(tǒng)一！
16 int fa = find(a), fb = find(b);
17 if (fa != fb)
18 {
19 father[fa] = fb;
20 tot --; // 統(tǒng)一了一次兩個(gè)陣營(yíng)的 BOSS ，所以需要添加的路徑的數(shù)目減一！
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 個(gè)點(diǎn)聯(lián)通所需要的最少邊的數(shù)目 ！
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); //輸出在已有基礎(chǔ)上還需要的邊的數(shù)目！
40 }
41 return 0;
42 }
43