题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1232
/* 典型的并查集习题,思路比较简单,只需要找出有几棵树就可以了 */ #include <iostream> using namespace std; const int MAX = 1001; int father[MAX]; int rank[MAX]; void Make_Set(const int n) { for (int i = 1; i <= n ; i++) { father[i] = i; rank[i] = 0; } } int Find_Set(const int x) { if (father[x] != x) father[x] = Find_Set(father[x]); return father[x]; } void Union (int x, int y) { x = Find_Set(x); y = Find_Set(y); if (x == y) return ; if (rank[x] > rank[y]) father[y] = x; else if (rank[x] < rank[y]) father[x] = y; else { rank[y]++; father[x] = y; } } int main () { int n, m; int a, b; while (cin >> n && n) { cin >> m; Make_Set(n); while (m--) { cin >> a >> b; Union(a, b); } int count = -1; for (int i = 1; i <= n; i++) if (father[i] == i) count ++; cout << count << endl; } }