hdu 1213 并查集

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

#include<iostream>
#include<cstdio>
using namespace std;
#define N 1000
int father[N];
void ufset()
{
    for(int i=0;i<N;i++)
        father[i]=-1;
}
int find(int x)
{
    int s;
    for(s=x;father[s]>=0;s=father[s]);
    while(s!=x)
    {
        int tmp=father[x];
        father[x]=s;
        x=tmp;
    }
    return x;
}
void Union(int R1,int R2)
{
    int r1=find(R1),r2=find(R2);
    int tmp=father[r1]+father[r2];
    if(father[r1]>father[r2])
    {
        father[r1]=r2;
        father[r2]=tmp;
    }
    else
    {
        father[r2]=r1;
        father[r1]=tmp;
    }
}
int main()
{
    int n,sum,m,x,y;
   // freopen("1.txt","r",stdin);
    scanf("%d",&n);
    while(n--)
    {
        int num=0;
        scanf("%d%d",&sum,&m);
        ufset();
        for(int i=0;i<m;i++)
         {
             scanf("%d%d",&x,&y);
             if(find(x)!=find(y))
             {
                Union(x,y);
                 num++;
             }
         }
         cout<<sum-num<<endl;
    }
}

  

上一篇:hdu 3635 Dragon Balls(并查集)


下一篇:hdu 1811Rank of Tetris (并查集 + 拓扑排序)