美文网首页
再贴一次并查集

再贴一次并查集

作者: 与卿__歌 | 来源:发表于2017-03-27 22:48 被阅读0次

    F - The Suspects POJ - 1611

    #include<stdio.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int pre[30005];
    int n,m,a,b;
    void unit()
    {
        for(int i=0;i<=n;i++)
        pre[i]=i;
    }
    int find(int x)
    {
        if(pre[x]==x)
        return x;
        else
        return find(pre[x]);
    }
    int Union(int a1,int b1)
    {
        int X=find(a1);
        int Y=find(b1);
        if(find(a1)!=find(b1))
        {
            pre[X]=Y; 
        }
    }
    int main()
    {
    while(  scanf("%d%d",&n,&m)!=EOF)
    {       
    if(n==0&&m==0)
    return 0;
            unit();
        for(int i=0;i<m;i++)
        {
            int x;
            scanf("%d",&x);
            scanf("%d",&a);
            for(int j=1;j<x;j++)
            {
                scanf("%d",&b);
                Union(a,b);
            }
        }
        int xx;
        xx=find(0);
    //  cout<<xx<<endl;
        int cnt=0;
        for(int i=0;i<=n;i++)
        {
            if(xx==find(i))
        //  printf("%d\n",i);
            cnt++;
        }
        printf("%d\n",cnt);
    }
    } 
    

    相关文章

      网友评论

          本文标题:再贴一次并查集

          本文链接:https://www.haomeiwen.com/subject/xojdottx.html