HDU 3560 Graph’s Cycle Component 【并查集】

并查集分组，deg必需为2才是circle

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100000+10;
int p[maxn],r[maxn],deg[maxn];
bool is_circle[maxn];
void init(int n)
{
    memset(p,-1,n<<2);
    memset(r,0,n<<2);
    memset(deg,0,n<<2);
}
int find(int x)
{
    int px=x,tmp;
    while(p[px]!=-1) px=p[px];
    while(x!=px)
    {
        tmp=p[x];
        p[x]=px;
        x=tmp;
    }
    return px;
}
void unio(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y) return;
    if(r[x]>r[y])
    {
        p[y]=x;return;
    }
    else
    {
        p[x]=y;if(r[x]==r[y]) r[y]++;
        return;
    }
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) return 0;
        init(n);
        int x,y;
        int a=0,b=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            unio(x,y);
            deg[x]++,deg[y]++;
        }
        for(int i=0;i<n;i++) 
            if(p[i]==-1)
            {
                a++;
                is_circle[i]=deg[i]==2;
            }
        for(int i=0;i<n;i++) find(i);
        for(int i=0;i<n;i++)
            if(p[i]!=-1&°[i]!=2)
                is_circle[p[i]]=false; 
        for(int i=0;i<n;i++)
            if(p[i]==-1&&is_circle[i]==true) b++;
        cout<<a<<' '<<b<<endl;
    }
}