題目描述

某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通的城鎮。省政府“暢通工程”的目標是使全省任何兩個城鎮間都可以實現交通（但不一定有直接的道路相連，只要互相間接通過道路可達即可）。問最少還需要建設多少條道路？

---

輸入

測試輸入包含若干測試用例。每個測試用例的第1行給出兩個正整數，分別是城鎮數目N ( < 1000 )和道路數目M；隨后的M行對應M條道路，每行給出一對正整數，分別是該條道路直接連通的兩個城鎮的編號。為簡單起見，城鎮從1到N編號。
注意:兩個城市之間可以有多條道路相通也就是說
3 3
1 2
1 2
2 1
這種輸入也是合法的
當N為0時，輸入結束，該用例不被處理。

---

輸出

對每個測試用例，在1行里輸出最少還需要建設的道路數目。

---

樣例輸入

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

---

提示

Huge input scanf is recommended.

---

算法思想

數組下標作為一個點，數組中存儲的元素作為其連接的另一個點，全聯通即：將所有下標對應的點歸攏到一個點上（也就是除了根節點，大家對應的都不是自己啦），相當于大家都跟一個點連接的話，當然是全聯通狀態啦。

---

代碼實現

---

尋找根節點

定義一個函數用來搜索給出結點的根節點，最終返回根節點的值（康康大家是不是來自同一地方嘛）

int find(int x){while(data[x]!=x){x=data[x];}return x;//返回根節點的值
}

當聯通關系不多，樹的深度不深的時候，用上一種方法無疑是很快的，但是如果聯通關系錯綜復雜，樹的深度很深，例如每層只有一個節點這種奇葩情況，遍歷搜索根節點就會很費時間，這時候就要用到“路徑壓縮“這一方法，即將所查詢節點的數組內容由”父節點“改為”祖宗節點“。

int find(int x){//尋找根節點int ans,tmp;ans = x;while(data[x]!=x){//x是根節點x=data[x];}while (ans != x) {//路徑壓縮tmp = data[ans];data[ans] = x;//數組內容直接儲存根節點，不再存儲父節點ans = tmp;//接下來壓縮父節點}return x;//返回根節點的值
}

---

匯總連接情況

將所給的兩個點的連接情況進行記錄，根節點不一樣的話說明是第一次告知兩個節點聯通，所以要把根節點改成一樣的， 一樣的話當然就是告知過了，不需要改變（大型認祖歸宗活動，哦兄弟我們是一家的，來來來族譜上記一下/哦兄弟我們是一家的，來來來……橋豆麻袋！族譜上記過了……不用記了誒）
?（淦！你忘了我們很久以前見過面的！！！）

void add(int x, int y){if(find(x)!=find(y)){data[find(x)]=find(y);}
}

---

完整代碼

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;int data[1003];int find(int x){//尋找根節點while(data[x]!=x){x=data[x];}return x;//返回根節點的值
}void add(int x, int y){if(find(x)!=find(y)){data[find(x)]=find(y);}
}int main(int argc, char const *argv[]) {int n,m;//n元素個數，m元素連接條數int x,y;//x,y是兩個相連的元素int flag;//未聯通的結點數while (cin >> n,n) {memset(data,0,sizeof (data));for (int i = 1; i <= n; i++) {data[i] = i;}for (cin >> m; m > 0; m--) {cin >> x;cin >> y;add(x,y);}flag = -1;for (int i = 1; i <= n; i++) {if(data[i]==i){flag++;//數組內容等于數組下標表示和自己聯通}}cout << flag << endl;}return 0;
}

關于flag的初值

其實難以理解的地方可能是flag的初值為什么要設置成-1，flag存儲的是數組內容等于數組下標的情況（自己連接自己的情況）有多少，每有一個就說明有一種連接種類，全聯通狀態只有一個這樣的情況——即根節點，也就是除了根節點和自己連接，其他的節點都不和自己連接，所以要把根節點這個情況排除在外，即flag初值為-1。
這樣一來，當全聯通時，只有根節點的data[i]=i，flag++，flag的值就為0，最后輸出flag的值也就是還需要修多少條路。

舉個栗子可能更方便理解
當輸入為
5 2
1 2
4 5
時
此時data數組的情況是（第四行）：
連接種類有三種：根節點為2的1、2連接、根節點為3的自己和自己連接、以及根節點為5的4、5連接。
此時data[i]=i的情況會出現3次，flag的終值也就是-1自加三次，也就是2，表示還需要修兩條路，舉個例子，3 2，3 4這樣修，那會出現什么情況呢？（為了便于理解拆分一下這個過程）


3 2的時候，3將2的根節點（也就是2本身）認作祖宗，3 4的時候，經過find函數查看族譜，誒大家祖宗不一樣誒但我們是一家人，那就一個祖宗認另一個祖宗為爹好了，這樣大家就在一起了，于是經過add函數修改族譜，3他爹2就認4他爹5當爹，1和3就成了5的乖孫孫。大家就是一家人了mua。（誰認誰當祖宗就看你怎么寫了哦吼，data[find(x)]=find(y）是后面的數當前面的數的祖宗，data[find(y)]=find(x）就是前面的當祖宗咯）