時(shí)間限制：1 s

空間限制：128 M

傳送門：https://oj.ahstu.cc/JudgeOnline/problem.php?id=1190

題目描述

機(jī)房里有若干臺(tái)電腦，其中有一些電腦已經(jīng)相互連接。如果A和B通過網(wǎng)線相連，并且B與C也通過網(wǎng)線相連，那么即便A和C之間沒有直接的網(wǎng)線相連，也可以認(rèn)為A和C是相連的。由于機(jī)房里的布線比較亂，并不是所有電腦都相互連通，請(qǐng)問在不變動(dòng)當(dāng)前布線情況下，最少要購買幾條網(wǎng)線才能使得機(jī)房所有電腦都兩兩連通。?

輸入

多組數(shù)據(jù)。每組數(shù)據(jù)第一行為整數(shù)N，M。N是電腦數(shù)量，M是機(jī)房已布置好的網(wǎng)線數(shù)量。接下來M行，每行為整數(shù)A，B。表明A，B之間通過一條網(wǎng)線直接相連。這里可以認(rèn)為網(wǎng)線是不分方向的，即A->B等價(jià)于B->A。?
（0 < N <= 200，0 <= M <= 10000，0 < A,B <= N 。） N=0和M=0為輸入結(jié)束，不需要處理。?

輸出

每組一個(gè)整數(shù)，即最少還要購買幾根網(wǎng)線。

樣例輸入?

4 2 1 2 2 3 4 0 1 0 0 0

樣例輸出

1 3 0

?

思路：用并查集存儲(chǔ)，若是連在一起的電腦就存到一個(gè)集合里面，最后判斷下有幾個(gè)集合，答案就是集合個(gè)數(shù)減一。在連接集合的時(shí)候設(shè)左邊為父結(jié)點(diǎn)。

代碼：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 int fina(int num); 7 int n, m, a[2010]; 8 9 int main() 10 { 11 cin >> n >> m; 12 13 while (n || m) 14 { 15 for (int i = 1; i <= n; i ++ ) 16 a[i] = i; 17 int x, y; 18 while (m -- ) 19 { 20 cin >> x >> y; 21 if (fina(x) != fina(y)) 22 { 23 a[fina(y)] = fina(x); 24 } 25 } 26 int ans = 0; 27 for (int i = 1; i <= n; i ++ ) 28 if (a[i] == i) ans ++ ; 29 30 cout << ans - 1 << endl; 31 cin >> n >> m; 33 memset(a,0,sizeof(a)); 34 } 35 return 0; 36 } 37 38 int fina(int num) 39 { 40 if (num == a[num]) return num; 41 else 42 { 43 a[num] = fina(a[num]); 44 return a[num]; 45 } 46 }

PS：應(yīng)該是安科 OJ 數(shù)據(jù)的問題，題目說的 n <= 200，但是數(shù)組開到210就會(huì)越界，開到2010才行（當(dāng)時(shí)debug了好久，555~）

轉(zhuǎn)載于:https://www.cnblogs.com/chuyds/p/11241019.html

總結(jié)

以上是生活随笔為你收集整理的安科 OJ 1190 连接电脑 （并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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