hdu-1232 畅通工程---并查集

题目链接：

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

题目大意：

中文题

解题思路：

直接并查集，判断有多少不同的根节点，答案就是根节点的数目-1，因为还需要建的道路就是根节点之间两两连接即可

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
int p[maxn];
int n, m;
set<int>s;
void init()
{
    s.clear();
    for(int i = 0; i < maxn; i++)p[i] = i;
}
int Find(int x)
{
    return x == p[x] ? x : p[x] = Find(p[x]);
}
int main()
{
    while(scanf("%d", &n) != EOF && n)
    {
        int x, y;
        init();
        scanf("%d", &m);
        while(m--)
        {
            scanf("%d%d", &x, &y);
            p[Find(x)] = Find(y);
        }
        for(int i = 1; i <= n; i++)
        {
            s.insert(Find(i));
        }
        cout<<(s.size() - 1)<<endl;
    }
    return 0;
}