Hdoj 3926 Hand in Hand

题目传送门

///题意：判断两个图是否同构

///@author just_sort
///2015/10/15 18:19
///Hand in Hand.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

struct node{
   int num,circle;
   friend bool operator<(const node &a,const node &b)
   {
       if(a.num==b.num)
        return a.circle<b.circle;
       return a.num<b.num;
   }
};

int fa[10010],ran[10010],iscircle[10010];
struct node arr1[10010];
struct node arr2[10010];
int len1,len2,n1,m1,n2,m2;

void init(int n)
{
    memset(iscircle,0,sizeof(iscircle));
    for(int i=1;i<=n;i++)
    {
        fa[i]=i,ran[i]=1;
    }
}

int Find(int x)
{
    if(x==fa[x])
        return x;
    return fa[x]=Find(fa[x]);
}


void Union(int x,int y)
{
    int a=Find(x),b=Find(y);
    if(a==b)
    {
        iscircle[a]=1;
        return ;
    }
    ran[a]+=ran[b];
    fa[b]=a;
}

void Input(int n,int m)
{
    int a,b;
    init(n);
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        Union(a,b);
    }
}

bool judge()
{
    if(len1!=len2)return false;
    sort(arr1,arr1+len1);
    sort(arr2,arr2+len2);
    for(int i=0;i<len1;i++)
    {
        if(arr1[i].num!=arr2[i].num)return false;
        if(arr1[i].circle!=arr2[i].circle)return false;
    }
    return true;
}

int main()
{
    int tt,ncase=1;
    cin>>tt;
    while(tt--)
    {
        cin>>n1>>m1;
        Input(n1,m1);
        len1=0;
        for(int i=1;i<=n1;i++)
        {
            if(i==Find(i))
            {
                arr1[len1].num=ran[i];
                arr1[len1++].circle=iscircle[i];
            }
        }
        cin>>n2>>m2;
        Input(n2,m2);
        len2=0;
        if(n1!=n2||m1!=m2)
        {
            printf("Case #%d: ",ncase++);
            puts("NO");
            continue;
        }
        else
        {
            for(int i=1;i<=n2;i++)
            {
                if(i==Find(i))
                {
                    arr2[len2].num=ran[i];
                    arr2[len2++].circle=iscircle[i];
                }
            }
        }
        printf("Case #%d: ",ncase++);
        if(judge())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}