ustc 1117

无根树同构

有两种方法，一种是确定其中一棵树，另一棵树枚举根节点。

一种是，利用拓扑排序，先确定其中一棵树。另一棵树，若拓扑后剩两个节点，则枚举这两个节点为根结点，否则，只需做一次。注意，无根树节点入度应为1。

 #include <iostream>

 #include <cstdio>

 using namespace std;

 const int N=;

 const int leaf_hash=;

 const int pt=;

 const int qt=;

 struct {

     int u,v;

     int next;

 }edge[N];

 int head[N];

 bool vis[N];

 int top,n,tot;

 void addedge(int u,int v){

     edge[tot].u=u;

     edge[tot].v=v;

     edge[tot].next=head[u];

     head[u]=tot++;

 }

 int hash(int u){

     vis[u]=true;

     int sum=; bool flag=false;

     for(int i=head[u];i!=-;i=edge[i].next){

         int v=edge[i].v;

         if(!vis[v]){

             flag=true;

             sum=sum*(pt^hash(v))%qt;

         }

     }

     if(flag) return sum;

     else return leaf_hash;

 }

 int main(){

     int T,i,u,v; int A,B,a,b;

     scanf("%d",&T);

     while(T--){

         scanf("%d",&n);

         memset(head,-,sizeof(head));

         tot=;

         for(i=;i<n;i++){

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

         }

         memset(vis,false,sizeof(vis));

         A=hash();

         memset(head,-,sizeof(head));

         tot=;

         for(i=;i<n;i++){

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

         }

         for(i=;i<=n;i++){

             memset(vis,false,sizeof(vis));

             B=hash(i);

             if(A==B){

                 break;

             }

         }

         if(i<=n) puts("same");

         else puts("different");

     }

     return ;

 }