文章目錄

• 題目描述
• 輸入
• 輸出
• 樣例輸入
• 樣例輸出
• 提示
• 算法思想
• 代碼實(shí)現(xiàn)
• • 尋找根節(jié)點(diǎn)
  • 匯總連接情況
  • 完整代碼
  • • 關(guān)于flag的初值

題目描述

某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計(jì)表，表中列出了每條道路直接連通的城鎮(zhèn)。省政府“暢通工程”的目標(biāo)是使全省任何兩個(gè)城鎮(zhèn)間都可以實(shí)現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過(guò)道路可達(dá)即可）。問(wèn)最少還需要建設(shè)多少條道路？

---

輸入

測(cè)試輸入包含若干測(cè)試用例。每個(gè)測(cè)試用例的第1行給出兩個(gè)正整數(shù)，分別是城鎮(zhèn)數(shù)目N ( < 1000 )和道路數(shù)目M；隨后的M行對(duì)應(yīng)M條道路，每行給出一對(duì)正整數(shù)，分別是該條道路直接連通的兩個(gè)城鎮(zhèn)的編號(hào)。為簡(jiǎn)單起見(jiàn)，城鎮(zhèn)從1到N編號(hào)。
注意:兩個(gè)城市之間可以有多條道路相通也就是說(shuō)
3 3
1 2
1 2
2 1
這種輸入也是合法的
當(dāng)N為0時(shí)，輸入結(jié)束，該用例不被處理。

---

輸出

對(duì)每個(gè)測(cè)試用例，在1行里輸出最少還需要建設(shè)的道路數(shù)目。

---

樣例輸入

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.

---

算法思想

數(shù)組下標(biāo)作為一個(gè)點(diǎn)，數(shù)組中存儲(chǔ)的元素作為其連接的另一個(gè)點(diǎn)，全聯(lián)通即：將所有下標(biāo)對(duì)應(yīng)的點(diǎn)歸攏到一個(gè)點(diǎn)上（也就是除了根節(jié)點(diǎn)，大家對(duì)應(yīng)的都不是自己啦），相當(dāng)于大家都跟一個(gè)點(diǎn)連接的話(huà)，當(dāng)然是全聯(lián)通狀態(tài)啦。

---

代碼實(shí)現(xiàn)

---

尋找根節(jié)點(diǎn)

定義一個(gè)函數(shù)用來(lái)搜索給出結(jié)點(diǎn)的根節(jié)點(diǎn)，最終返回根節(jié)點(diǎn)的值（康康大家是不是來(lái)自同一地方嘛）

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

當(dāng)聯(lián)通關(guān)系不多，樹(shù)的深度不深的時(shí)候，用上一種方法無(wú)疑是很快的，但是如果聯(lián)通關(guān)系錯(cuò)綜復(fù)雜，樹(shù)的深度很深，例如每層只有一個(gè)節(jié)點(diǎn)這種奇葩情況，遍歷搜索根節(jié)點(diǎn)就會(huì)很費(fèi)時(shí)間，這時(shí)候就要用到“路徑壓縮“這一方法，即將所查詢(xún)節(jié)點(diǎn)的數(shù)組內(nèi)容由”父節(jié)點(diǎn)“改為”祖宗節(jié)點(diǎn)“。

int find(int x){//尋找根節(jié)點(diǎn)int ans,tmp;ans = x;while(data[x]!=x){//x是根節(jié)點(diǎn)x=data[x];}while (ans != x) {//路徑壓縮tmp = data[ans];data[ans] = x;//數(shù)組內(nèi)容直接儲(chǔ)存根節(jié)點(diǎn)，不再存儲(chǔ)父節(jié)點(diǎn)ans = tmp;//接下來(lái)壓縮父節(jié)點(diǎn)}return x;//返回根節(jié)點(diǎn)的值 }

---

匯總連接情況

將所給的兩個(gè)點(diǎn)的連接情況進(jìn)行記錄，根節(jié)點(diǎn)不一樣的話(huà)說(shuō)明是第一次告知兩個(gè)節(jié)點(diǎn)聯(lián)通，所以要把根節(jié)點(diǎn)改成一樣的， 一樣的話(huà)當(dāng)然就是告知過(guò)了，不需要改變（大型認(rèn)祖歸宗活動(dòng)，哦兄弟我們是一家的，來(lái)來(lái)來(lái)族譜上記一下/哦兄弟我們是一家的，來(lái)來(lái)來(lái)……橋豆麻袋！族譜上記過(guò)了……不用記了誒）
?（淦！你忘了我們很久以前見(jiàn)過(guò)面的！！！）

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){//尋找根節(jié)點(diǎn)while(data[x]!=x){x=data[x];}return x;//返回根節(jié)點(diǎn)的值 }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元素個(gè)數(shù)，m元素連接條數(shù)int x,y;//x,y是兩個(gè)相連的元素int flag;//未聯(lián)通的結(jié)點(diǎn)數(shù)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++;//數(shù)組內(nèi)容等于數(shù)組下標(biāo)表示和自己聯(lián)通}}cout << flag << endl;}return 0; }

關(guān)于flag的初值

其實(shí)難以理解的地方可能是flag的初值為什么要設(shè)置成-1，flag存儲(chǔ)的是數(shù)組內(nèi)容等于數(shù)組下標(biāo)的情況（自己連接自己的情況）有多少，每有一個(gè)就說(shuō)明有一種連接種類(lèi)，全聯(lián)通狀態(tài)只有一個(gè)這樣的情況——即根節(jié)點(diǎn)，也就是除了根節(jié)點(diǎn)和自己連接，其他的節(jié)點(diǎn)都不和自己連接，所以要把根節(jié)點(diǎn)這個(gè)情況排除在外，即flag初值為-1。
這樣一來(lái)，當(dāng)全聯(lián)通時(shí)，只有根節(jié)點(diǎn)的data[i]=i，flag++，flag的值就為0，最后輸出flag的值也就是還需要修多少條路。

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


3 2的時(shí)候，3將2的根節(jié)點(diǎn)（也就是2本身）認(rèn)作祖宗，3 4的時(shí)候，經(jīng)過(guò)find函數(shù)查看族譜，誒大家祖宗不一樣誒但我們是一家人，那就一個(gè)祖宗認(rèn)另一個(gè)祖宗為爹好了，這樣大家就在一起了，于是經(jīng)過(guò)add函數(shù)修改族譜，3他爹2就認(rèn)4他爹5當(dāng)?shù)?#xff0c;1和3就成了5的乖孫孫。大家就是一家人了mua。（誰(shuí)認(rèn)誰(shuí)當(dāng)祖宗就看你怎么寫(xiě)了哦吼，data[find(x)]=find(y）是后面的數(shù)當(dāng)前面的數(shù)的祖宗，data[find(y)]=find(x）就是前面的當(dāng)祖宗咯）

總結(jié)

以上是生活随笔為你收集整理的一学就废的并查集它来了的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。