題目意思就是判斷兩個圖是不是同構，就是兩個圖是不是一樣，由於該題的圖是非常特殊的，度只能為2，所以圖是由若干個鏈組成，或是若干個環，即1--->2--->3--->1,,,,,,1---》2--->3;;;這兩個圖是不一樣的，特殊的，(1--->1,,,,2--->2,,,,), 1，，，，2；這兩個圖是不一樣的；前面一個是兩個自環，後面的是兩個點；這題剛開始各種ORZ，，，，ORZ，，，，OTL，，，弱爆了。。。。。，加油喔；
[cpp]
#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[u]=true;
cnt++;
int d=M[u].size(),v;
for(int i=0;i<d;i++)
{
v=M[u][i];
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[i].clear();
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
M[a].push_back(b);
M[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
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[i]!=y.c[i])
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[i]!=y.r[i])
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;
}
作者：Java_beginer1
