题目：http://acm.hdu.edu.cn/showproblem.php?pid=1232
/************************************************************************/ /* hdu 畅通工程最简单的并查集题目大意：求建设最少的路径使得道路畅通解题思路：并查集，利用并查集,合并可达的集合，即连通的地方为一个集合，计算集合数目；集合数目减少1即为需要修道路数目 */ /************************************************************************/#include <stdio.h> #include <string.h> #include <algorithm>const int N = 1001; int root[N]; int count;int find_root(int a) {if(root[a] == a)return a;return root[a] = find_root(root[a]); }void union_set(int a, int b) {int x = find_root(a);int y = find_root(b);if(x==y)return;else{root[y] = x;} }int main() {int m,n,x,y;while(scanf("%d%d",&n,&m) && n != 0){for (int i = 1; i <= n; i++)root[i] = i;count = 0;for (int j = 0; j < m; j++){scanf("%d%d",&x,&y);union_set(x,y);}for (int i = 1; i <= n; i++){if(root[i] == i)count++;}printf("%d\n",count-1);}return 0; }
