首页 > 代码库 > 【HDU1232】畅通工程(并查集基础题)

【HDU1232】畅通工程(并查集基础题)

裸敲并查集,很水一次AC

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cctype> 6 #include <cmath> 7 #include <algorithm> 8 #include <numeric> 9 #include <string>10 11 #pragma comment(linker, "/STACK:102400000,102400000")12 using namespace std;13 14 int cnt = 0;15 const int V = 1005;16 int father[V];17 18 int getFather (int x) {19     if (father[x] != x) {20         father[x] = getFather (father[x]);21     }22     return father[x];23 }24 25 void Union (int p, int q) {26     int x = getFather (p);27     int y = getFather (q);28     if (x != y) {29         father[y] = x;30         cnt ++;31     }32 }33 34 int main () {35     int n, road_n;36     while (~scanf("%d", &n)) {37         if (!n) break;38         scanf("%d", &road_n);//cin >> road_n;39         cnt = 0;40         for (int i = 0; i <= n; ++ i) {41             father[i] = i;42         }43 44         for (int i = 0 ; i < road_n; ++ i) {45             int x, y; //cin >> x >> y;46             scanf("%d%d", &x, &y);47             Union (x, y);48         }49         //cout << "cnt :   " << cnt << endl;50         cout << n - 1 - cnt << endl;51     }52     return 0;53 }