【HDOJ】畅通工程（并查集）

通畅工程（HDOJ）

思路：模板并查集

#include<bits/stdc++.h>
using namespace std;
int f[1007];
int find(int x)
{
    if(f[x]==x) return x;
    else return  f[x]=find(f[x]);
}
void merge(int x,int y)
{
    int fx,fy;
    fx = find(x);
    fy = find(y);
    if(fx != fy)
      f[fx]=fy;
}
int main()
{
    int n,m,i,x,y;
    while(cin>>n>>m&&n)
    {
        for(i=1;i<=n;i++)
        {
            f[i]=i;
        }
        for(i=0;i<m;i++)
        {
            cin>>x>>y;
            merge(x,y);
        }
        int sum=0;
        for(i=1;i<=n;i++)
        {
            if(f[i]==i)
                sum++;
        }
        cout<<sum-1<<endl;
    }
    return 0;
}