HDu 3926 Hand in Hand【同構図】

文書ディレクトリ

タイトルリンク:

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=3926 题意:2つの図を与えて、彼が同构図以前に一度だけ同构の问题を见たことがあるかどうかを判断して、构の意味さえ忘れてT_Tこの2018夏休み牛客多校(一)Dは私が初めてで唯一同構造を聞いた時
2つの図が同じ構造であるかどうかを判断するのは難しいようですが、牛客多校はそれが8つの頂点のようですね.私たちのこの問題点は多いですが、1人が2つの手しかないという制限条件があります.つまり、構成された図の様子はあのめちゃくちゃな図ではありません.リングか、チェーンか、この2つのものをすべて探し出してそれから対比して同じかどうかを見て、この問題は書くのが少し煩わしいと感じて、1つの模擬問題と同じで、私は初期化を忘れて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");
	}
}