一道很好的并查集题目。。。
#include<stdio.h> #include<string.h> #include<set> using namespace std; const int maxn = 1010; int fa[maxn]; int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); } #define LOCAL int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int n, m; while(scanf("%d", &n), n != 0) { for(int i = 1; i <= n; i++) fa[i] = i; scanf("%d", &m); int a, b; for(int i = 0; i < m; i++) { scanf("%d%d", &a, &b); int x = find(a); int y = find(b); if(x != y) fa[y] = x; } set<int> ans; for(int i = 1; i <= n; i++) { int x = find(i); ans.insert(x); } printf("%d/n", ans.size()-1); } return 0; }
