首页 > 代码库 > ustc 1117

ustc 1117

2024-07-06 16:21:01   225人阅读

无根树同构

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

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

 

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 const int N=1005;
 6 const int leaf_hash=2099;
 7 const int pt=9323;
 8 const int qt=8719;
 9 
10 struct {
11     int u,v;
12     int next;
13 }edge[N];
14 int head[N];
15 bool vis[N];
16 int top,n,tot;
17 
18 void addedge(int u,int v){
19     edge[tot].u=u;
20     edge[tot].v=v;
21     edge[tot].next=head[u];
22     head[u]=tot++;
23 }
24 
25 int hash(int u){
26     vis[u]=true;
27     int sum=1; bool flag=false;
28     for(int i=head[u];i!=-1;i=edge[i].next){
29         int v=edge[i].v;
30         if(!vis[v]){
31             flag=true;
32             sum=sum*(pt^hash(v))%qt;
33         }
34     }
35     if(flag) return sum;
36     else return leaf_hash;
37 }
38 
39 int main(){
40     int T,i,u,v; int A,B,a,b;
41     scanf("%d",&T);
42     while(T--){
43         scanf("%d",&n);
44         memset(head,-1,sizeof(head));
45         tot=0;
46         for(i=1;i<n;i++){
47             scanf("%d%d",&u,&v);
48             addedge(u,v);
49             addedge(v,u);
50         }
51         memset(vis,false,sizeof(vis));
52         A=hash(1);
53         memset(head,-1,sizeof(head));
54         tot=0;
55         for(i=1;i<n;i++){
56             scanf("%d%d",&u,&v);
57             addedge(u,v);
58             addedge(v,u);
59         }
60         for(i=1;i<=n;i++){
61             memset(vis,false,sizeof(vis));
62             B=hash(i);
63             if(A==B){
64                 break;
65             }
66         }
67         if(i<=n) puts("same");
68         else puts("different");
69     }
70     return 0;
71 }
View Code

 


联系
我们