?

思路： 當(dāng)圖中的集合(連通子圖)個(gè)數(shù)為1并且邊數(shù)等于頂點(diǎn)數(shù)-1(即改圖恰好為一棵生成樹)時(shí)，輸出Yes.

此題的坑：(1) 如果只輸入0 0算作一組數(shù)據(jù)的話答案應(yīng)該輸出Yes

　　　　　(2) 輸入數(shù)據(jù)可能并不是連通圖，有可能一開始不連通，所以最后一定要判斷其連通子圖個(gè)數(shù)是不是1

1 #include<iostream> 2 #include<vector> 3 #include<string> 4 #include<cmath> 5 #include<set> 6 #include<algorithm> 7 #include<cstdio> 8 #include<map> 9 #include<cstring> 10 11 using namespace std; 12 13 int Tree[100100]; 14 15 int findRoot(int x) 16 { 17 if(Tree[x] == -1) 18 return x; 19 int tmp = findRoot(Tree[x]); 20 Tree[x] = tmp; 21 return tmp; 22 } 23 24 int main() 25 { 26 int a, b; 27 set<int> Set; // 使用Set保存圖中的所有頂點(diǎn)編號(hào) 28 for(int i = 0; i <= 100000; ++i) 29 Tree[i] = -1; 30 31 int rimCnt = 0; 32 while(cin >> a >> b) 33 { 34 if(a == -1 && b == -1) 35 break; 36 37 if(a == 0 && b == 0) 38 { 39 if(rimCnt == 0) // 只有輸入一組數(shù)據(jù)0 0的時(shí)候，應(yīng)該輸出Yes 40 { 41 cout << "Yes" << endl; 42 continue; 43 } 44 int Vcnt = Set.size(); // 頂點(diǎn)計(jì)數(shù) 45 int Scnt = 0; // 圖中的連通子圖(集合)個(gè)數(shù) 46 for(set<int>::iterator iter = Set.begin(); iter != Set.end(); ++iter) 47 { 48 if(Tree[*iter] == -1) 49 { 50 Scnt++; 51 } 52 } 53 54 // 當(dāng)圖中的集合只有一個(gè)并且總邊數(shù)等于頂點(diǎn)數(shù)-1的時(shí)候，輸出Yes 55 if(Scnt == 1 && rimCnt == Vcnt - 1) 56 { 57 cout << "Yes" << endl; 58 } 59 else 60 { 61 cout << "No" << endl; 62 } 63 64 for(int i = 0; i <= 100000; ++i) 65 Tree[i] = -1; 66 Set.clear(); // 清空集合 67 rimCnt = 0; // 邊數(shù)置零 68 continue; 69 } 70 else 71 { 72 rimCnt++; // 邊計(jì)數(shù) 73 Set.insert(a); 74 Set.insert(b); 75 int ra = findRoot(a); 76 int rb = findRoot(b); 77 if(ra != rb) 78 { 79 Tree[ra] = rb; 80 } 81 } 82 83 } 84 85 return 0; 86 }

?

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

總結(jié)

以上是生活随笔為你收集整理的小希的迷宫 HDU - 1272 (并查集)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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