HDU-3926hand in hand（找同构图）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=3926

题意：给两个图，问是否是同构图；

并查集裸题，判断一下为环为链即可；

给节点排序，初始化为1；

代码：

#include<bits/stdc++.h>
#define ll long long
const int maxn=200020;
const int inf=-0x3f3f3f;
using namespace std;

ll gcd(int a,int b){return b==0?a:gcd(b,a%b);}
ll lcm(int a,int b){return gcd(a,b)/a*b;}
int fa1[maxn],fa2[maxn];
int n1,m1,n2,m2;

struct node{
    int son;
    int check;
}g1[maxn],g2[maxn];

bool cmp(node a,node b)
{
    if(a.son==b.son)
      return a.check<b.check;
    else
     return a.son<b.son;
}

int find(int fa[],int x) {return x==fa[x]?x:fa[x]=find(fa,fa[x]);}

void Union(int fa[],node g[],int x,int y)
{
    int fx=find(fa,x);
    int fy=find(fa,y);
    if(fx==fy)//图为环的情况 
      g[fx].check=1;
    else
    {
        if( g[fx].son>=g[fy].son )//结点相加，把小的合并进大的里边
        {
            fa[fy]=fx;
            g[fx].son+=g[fy].son;
        }
        else
        {
            fa[fx]=fy;
            g[fy].son+=g[fx].son;
        }
    }
    return ;
}

int compare()
{
    sort( g1+1,g1+n1+1,cmp);
    sort( g2+1,g2+n2+1,cmp);
    for( int i=1; i<=n1; i++ )
    {
        if(g1[i].son!=g2[i].son || (g1[i].son==g2[i].son&&g1[i].check!=g2[i].check ))
            return 0;
    }
    return 1;
}

void solve(int k)
{
    int flag=1;
    for(int i=1; i<=maxn-5; i++) 
    {
        fa1[i]=i,fa2[i]=i;
    }
    
    scanf("%d%d",&n1,&m1);
    for(int i=1; i<=n1; i++)
    {
        g1[i].son=1,  g2[i].son=1;
        g1[i].check=0,g2[i].check=0;
    }
    for(int i=1; i<=m1; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        Union(fa1,g1,x,y);
    }

    scanf("%d%d",&n2,&m2);
    if(m1!=m2) flag=0;
    for(int i=1; i<=m2; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(flag)
         Union(fa2,g2,x,y);
    }
    flag=compare();
    
    if(flag)
      printf("Case #%d: YES
",k);
    else
      printf("Case #%d: NO
",k);
    
    return ;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1; i<=t; i++)
     solve(i);
    return 0;}