hdu 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;
}