首页 > 代码库 > 【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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。