并查集在解决图的连通性非常高效,hdu1232采用并查集,可以很快解决,代码如下:
/* * hdu1232.cpp * * Created on: 2012-5-10 * Author: ict */ #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define CLR(arr, what) memset(arr, what, sizeof(arr)) #define N 1001 int pre[N]; int Find_Set(int x) //递归+路径压缩 { return pre[x] == -1 ? x : (pre[x] = Find_Set(pre[x])); } void Make_Set(int x, int y) //无按秩合并 { int root1 = Find_Set(x); int root2 = Find_Set(y); if(root1 != root2) pre[root2] = root1; } int main() { int i, j; int n, m; int a, b; int count; while(1) { scanf("%d", &n); if(!n) break; scanf("%d", &m); CLR(pre, -1); for(i = 0; i < m; i++) { scanf("%d %d", &a, &b); Make_Set(a, b); } count = 0; for(i = 1; i <= n; i++) { if(pre[i] == -1) count++; } printf("%d\n", count - 1); } return 0; }