文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3926
题意：给两个图，判断他是否是同构图
以前只见过一次同构的题，连同构的意思都忘了T_T
这个2018暑假牛客多校(一)D是我第一次也是唯一一次听到同构的时候

要判断两个图是不是同构貌似是很难的，牛客多校那个好像才8个顶点哇，而我们这道题点虽然比较多，但是有个很关键的限制条件
就是一个人只有两只手，也就是说构成的图的样子不可能是那种乱七八糟的图，<mark>要么是个环，要么是条链</mark>，把这这两种东西都找出来然后对比看是不是一样的就行了，这题写起来感觉有点烦，跟个模拟题一样，我忘了初始化也贡献了一发WA

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int maxn=1e4+5;
const int MOD=1e9+7;
int in1[maxn],in2[maxn];
int fa1[maxn],fa2[maxn];
int Find1(int x)
{
	if(x==fa1[x])return x;
	else return fa1[x]=Find1(fa1[x]);
}
int Find2(int x)
{
	if(x==fa2[x])return x;
	else return fa2[x]=Find2(fa2[x]);
}
map<int,int>Mp1,Mp2;
vector<int>vec1[maxn],vec2[maxn];//保存fa相同的点，用来判断是环还是链 
int judge(vector<int>v,int cmd)
{
	if(cmd==1)
	{
		for(int i=0;i<v.size();i++)if(in1[v[i]]==1)return 1;//如果是链的话，那么有一个点的度就是1 
		return 2;//不然就都是2 
	}
	else
	{
		for(int i=0;i<v.size();i++)if(in2[v[i]]==1)return 1;
		return 2;
	}
	return 0;//不然就是单点 
}
int main()
{
	int T;
	cin>>T;
	for(int Case=1;Case<=T;Case++)
	{
		for(int i=1;i<=10000;i++)vec1[i].clear(),vec2[i].clear();
		Mp1.clear();
		Mp2.clear();
		memset(in1,0,sizeof in1);
		memset(in2,0,sizeof in2);
		cin>>N1>>M1;
		for(int i=1;i<=N1;i++)fa1[i]=i;
		for(int i=1;i<=M1;i++)
		{
			int u,v;
			cin>>u>>v;
			in1[u]++,in1[v]++;
			u=Find1(u),v=Find1(v);
			fa1[u]=v;
		}
		
		cin>>N2>>M2;
		for(int i=1;i<=N2;i++)fa2[i]=i;
		for(int i=1;i<=M2;i++)
		{
			int u,v;
			cin>>u>>v;
			in2[u]++,in2[v]++;
			u=Find2(u),v=Find2(v);
			fa2[u]=v;
		}
		for(int i=1;i<=N1;i++)fa1[i]=Find1(fa1[i]),fa2[i]=Find2(fa2[i]); 
		vector<int>root1,root2;
		for(int i=1;i<=N1;i++)
		{
			if(fa1[i]==i)root1.push_back(i);
			vec1[fa1[i]].push_back(i);
		}
		
		for(int i=1;i<=N2;i++)
		{
			if(fa2[i]==i)root2.push_back(i);
			vec2[fa2[i]].push_back(i);
		}
		vector<int>lian1,quan1,lian2,quan2;
		for(int i=0;i<root1.size();i++)
		{
			int t=judge(vec1[root1[i]],1);
			if(t==1)lian1.push_back(vec1[root1[i]].size());
			else if(t==2)quan1.push_back(vec1[root1[i]].size());
		}
		for(int i=0;i<root2.size();i++)
		{
			int t=judge(vec2[root2[i]],2);
			if(t==1)lian2.push_back(vec2[root2[i]].size());
			else if(t==2)quan2.push_back(vec2[root2[i]].size());
		}
		cout<<"Case #"<<Case<<": ";
		if(lian1.size()!=lian2.size()||quan1.size()!=quan2.size())//这里最好特判一哈，不然后面长度不同要RE 
		{
			puts("NO");
			continue;
		}
		sort(lian1.begin(),lian1.end());
		sort(lian2.begin(),lian2.end());
		sort(quan1.begin(),quan1.end());
		sort(quan2.begin(),quan2.end());
		int flag=1;
		for(int i=0;i<lian1.size();i++)
		{
			if(lian1[i]!=lian2[i])flag=0;
		}
		for(int i=0;i<quan1.size();i++)
		{
			if(quan1[i]!=quan2[i])flag=0;
		}
		if(flag)puts("YES");
		else puts("NO");
	}
}