1232畅通工程(并查集)

http://acm.hdu.edu.cn/showproblem.php?pid=1232

#include <stdio.h>
#include <stdlib.h>

#define MAXN 2000

int v[MAXN], u[MAXN], p[MAXN];
int icount;

int find_f(int x){return p[x] == x ? x : (p[x]=find_f(p[x]));}


int main(){
    int n, m, i;

    while(scanf("%d", &n) == 1 && n != 0){
        scanf("%d", &m);
        icount = n-1;   //最少需要的边
        for(i=0; i<m; i++) scanf("%d %d", &v[i], &u[i]);
        for(i=1; i<=n; i++) p[i] = i;   //初始化并查集, 边的编号是从1开始的
        for(i=0; i<m; i++){
            int x = find_f(v[i]), y = find_f(u[i]);
            if(x != y) {p[x] = y; icount--;}
        }
        printf("%d\n", icount);
    }
    return 0;
}