模板

并查集模板

#include<stdio.h>
#define maxn 100005                //定义maxn   
using namespace std;
int s[maxn];
int find(int x)
{
    if(s[x]==x)
    {
        return x;
    }
    else
    {
        return find(s[x]);             //找上一个，一直到一样，即源头 
    }
}
void Union(int x,int y)
{
    int x1,y1;
    x1=find(x);
    y1=find(y);
    if(x1!=y1)
    {
        s[y1]=x1;
    }
}
int main()
{
    int i,j,count,a,b;
    for(i=0;i<=maxn;i++)                       //用了maxn; 
    {
        s[i]=i;             //赋值 
    }
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        if(a==0&&b==0)                //跳出循环 
        {
            break;
        }
        if(find(a)==find(b))            //判断a,b是否联通 
        {
            printf("YES  *\n");
        }
        else
        {
            printf("NO\n");
            Union(a,b);               //联通a,b      把b给a（以a为源头） 
        //  printf("a=%d     b=%d\n",find(a),find(b));
            if(find(a)==find(b))
            {
                printf("YES  #\n");
            }
            else
            {
                printf("NO   !!!!!\n");       //都联通了，好像已经没用了。。。。。。 
            }
        }
    }
    count=0;
    for(j=0;j<maxn;j++)              //用了maxn; 
    {
        if(s[j]==j)
        {
            count++;
        }
    }
    printf("count=%d\n",count);            //输出还有多少团体，联通的算一个了 
    return 0;
}