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

13719654321

　　题目意思就是判断两个图是不是同构，就是两个图是不是一样，由于该题的图是非常特殊的，度只能为2，所以图是由若干个链组成，或是若干个环，即1--->2--->3--->1,,,,,,1---》2--->3;;;这两个图是不一样的，特殊的，(1--->1,,,,2--->2,,,,), 1，，，，2；这两个图是不一样的；前面一个是两个自环，后面的是两个点；这题刚开始各种ORZ，，，，ORZ，，，，OTL，，，弱爆了。。。。。 ，加油喔；

#include<cstdio>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
bool vis[10005];
vector<int>M[10005];
const int INF=9999999;
struct node
{
int c_num,r_num;
int c[10005],r[10005];
}x,y;
void dfs(int u,int &cnt,int fa,int &flag)
{
vis=true;
cnt++;
int d=M.size(),v;
for(int i=0;i<d;i++)
{
v=M;
if(v==fa)
continue;
if(vis[v])
flag=1;
if(!vis[v])
{
dfs(v,cnt,u,flag);
}
}
}
void slove(node &T,int n,int m)
{
memset(vis,false,sizeof(vis));
T.r_num=T.c_num=0;
memset(T.c,0x3f,sizeof(T.c));
memset(T.r,0xff,sizeof(T.r));
for(int i=0;i<=n;i++)
M.clear();
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
M[a].push_back(b);
M.push_back(a);
}
for(int i=1;i<=n;i++)
{
if(!vis)
{
int flag=0;
int cnt=1;
dfs(i,cnt,INF,flag);
if(flag)
{
T.c[T.c_num++]=cnt;
// printf("Case %d shi环 cnt= %d\n",i,cnt);
}else{
T.r[T.r_num++]=cnt;
// printf("Case %d shi 链链 cnt= %d\n",i,cnt);
}
}
}
}
bool ok()
{
//printf("1\n");
//printf("x.c_num= %d  y.c_num= %d\n",x.c_num,y.c_num);
if(x.c_num!=y.c_num)
return false;
sort(x.c,x.c+x.c_num);
sort(y.c,y.c+y.c_num);
//printf("2\n");
for(int i=0;i<x.c_num;i++)
{
if(x.c!=y.c)
return false;
}
//printf("3\n");
if(x.r_num!=y.r_num)
return false;
sort(x.r,x.r+x.r_num);
sort(y.r,y.r+y.r_num);
//printf("4\n");
for(int i=0;i<x.r_num;i++)
if(x.r!=y.r)
return false;
//printf("5\n");
return true;
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
int n,m;
scanf("%d%d",&n,&m);
slove(x,n,m);
scanf("%d%d",&n,&m);
slove(y,n,m);
if(ok())
printf("Case #%d: YES\n",i);
else
printf("Case #%d: NO\n",i);
}
return 0;
}