hdu-3926-Hand in Hand-并查集

判断 两个图 是否同构。。

用了并查集。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
#define ll long long

int n,m;
struct node
{
	int fu;
	int sum;
	int flag;
}p[10010],p1[10010],p2[10010];
int root(int h)
{
	if(p[h].fu==-1) return h;
	else return p[h].fu=root(p[h].fu);
}
void merge(int a,int b)
{
	a=root(a);
	b=root(b);
	p[a].fu=b;
	p[b].sum+=p[a].sum;
}
int cmp(node a,node b)
{
	if(a.sum==b.sum)
		return a.flag<b.flag;
	return a.sum<b.sum;
}

int main()
{
	int i,j,k;
	int t;
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++){
			p[i].fu=-1;
			p[i].sum=1;
			p[i].flag=0;
		}
		while(m--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			int ta=root(a);
			int tb=root(b);
			if(ta!=tb)
				merge(a,b);
			else
				p[ta].flag=1;
		}
		int ans=0;
		for(i=1;i<=n;i++)
		{
			if(p[i].fu==-1)
			{
				p1[ans].flag=p[i].flag;
				p1[ans].sum=p[i].sum;
				ans++;
			}
		}
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++){
			p[i].fu=-1;
			p[i].sum=1;
			p[i].flag=0;
		}
		while(m--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			int ta=root(a);
			int tb=root(b);
			if(ta!=tb)
				merge(a,b);
			else
				p[ta].flag=1;
		}
		int ans1=0;
		for(i=1;i<=n;i++)
		{
			if(p[i].fu==-1)
			{
				p2[ans1].flag=p[i].flag;
				p2[ans1].sum=p[i].sum;
				ans1++;
			}
		}
		if(ans!=ans1)
			printf("Case #%d: NO\n",k);
		else
		{
			sort(p1,p1+ans,cmp);
			sort(p2,p2+ans,cmp);
			int ff=0;
			for(i=0;i<ans;i++)
			{
				if(p1[i].sum==p2[i].sum && p1[i].flag==p2[i].flag)
					continue;
				else
				{
					ff=1;
					break;
				}
			}
			if(ff==0)
				printf("Case #%d: YES\n",k);
			else
				printf("Case #%d: NO\n",k);
		}
	}
}