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

题目意思就是判断两个图是不是同构，就是两个图是不是一样，由于该题的图是非常特殊的，度只能为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

补充：软件开发 , C++ ,