hdoj3926

这题多写了个continue。。检查n久。。
由于只有两只手,所以:
1.若形成的图不连通,则几个连通分量或为环,或为链。
2.若形成的图连通,则或为环,或为链。
判断是否同构的步骤:
1,顶点数是否相同
2.并查集:把连通的点并入一个集合,同时更新权cnt[],用于表示集合元素个数。
3.在合并时注意判断是否形成环。(注意a b b a这种情况,这是不能认为是环)
4.将两个图的各个连通分量所含顶点数及其形状存入两个数组,进行排序
5.如果两个图的连通分量数不同,则不同构。
5.一一对比,不同则不同构。

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
int bin1[10010];
int cnt1[10010];
bool shape1[10010];
int bin2[10010];
int cnt2[10010];
bool shape2[10010];
vector<int> head[10010];
typedef struct Node{
	int cnt;
	bool shape;
}node;
bool cmp(node a,node b)
{
	if(a.cnt!=b.cnt)
		return a.cnt<b.cnt;
	return a.shape<b.shape;
}
int find(int*ufs,int x)
{
	int r=x;
	while(ufs[r]!=r)
		r=ufs[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=ufs[t];
		ufs[t]=r;
		t=tmp;
	}
	return r;
}
void merge(int*ufs,int*ufs_cnt,int fx,int fy)
{
	ufs[fx]=fy;
	ufs_cnt[fy]+=ufs_cnt[fx];
	return;
}
int main()
{
	int t;
	int i,cases=0;
	scanf("%d",&t);
	while(t--)
	{
		int n1,m1,n2,m2;
		scanf("%d %d",&n1,&m1);
		for(i=1;i<=n1;i++)
		{
			bin1[i]=i;
			cnt1[i]=1;
			shape1[i]=0;
			head[i].clear();
		}
		for(i=1;i<=m1;i++)
		{
			int u,v;
			bool tmp=0;
			scanf("%d %d",&u,&v);
			if(u>v)
			{
				int t=u;
				u=v;
				v=t;
			}
			if(binary_search(head[u].begin(),head[u].end(),v)==0)
			{
				head[u].push_back(v);
			}
			else
				tmp=1;
			int fx=find(bin1,u);
			int fy=find(bin1,v);
			if(fx!=fy)
				merge(bin1,cnt1,fx,fy);
			else
			{
				if(tmp==0)
					shape1[fy]=1;
			}
			
		}
		scanf("%d %d",&n2,&m2);
		for(i=1;i<=n2;i++)
		{
			bin2[i]=i;
			cnt2[i]=1;
			shape2[i]=0;
			head[i].clear();
		}
		for(i=1;i<=m2;i++)
		{
			int u,v;
			bool tmp=0;
			scanf("%d %d",&u,&v);
			if(u>v)
			{
				int t=u;
				u=v;
				v=t;
			}
			if(binary_search(head[u].begin(),head[u].end(),v)==0)
			{
				head[u].push_back(v);
			}
			else
				tmp=1;
			int fx=find(bin2,u);
			int fy=find(bin2,v);
			if(fx!=fy)
				merge(bin2,cnt2,fx,fy);
			else
			{
				if(tmp==0)
					shape2[fy]=1;
			}
			
		}
		bool flag=1;
		if(n1!=n2)
		{
			flag=0;
		}
		node ans1[10010];
		node ans2[10010];
		int count1=0,count2=0;
		for(i=1;i<=n1;i++)
		{
			if(bin1[i]==i)
			{
				ans1[++count1].cnt=cnt1[i];
				ans1[count1].shape=shape1[i];
			}
			if(bin2[i]==i)
			{
				ans2[++count2].cnt=cnt2[i];
				ans2[count2].shape=shape2[i];
			}
		}
		if(count1!=count2)
		{
			flag=0;
		}
		else
		{
			sort(ans1+1,ans1+1+count1,cmp);
			sort(ans2+1,ans2+1+count2,cmp);
			for(i=1;i<=count1;i++)
				if(ans1[i].cnt!=ans2[i].cnt || ans1[i].shape!=ans2[i].shape)
				{
					flag=0;
				}
		}
		if(flag)
			printf("Case #%d: YES\n",++cases);
		else
			printf("Case #%d: NO\n",++cases);
	
	}

//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>