Description
树是一种很常见的数据结构。
我们把N个点，N-1条边的连通无向图称为树。
若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。
对于两个树T1和T2，如果能够把树T1的所有点重新标号，使得树T1和树T2完全相
同，那么这两个树是同构的。也就是说，它们具有相同的形态。
现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。
对于100%的数据，$1\leq N ,M \leq 50$。
Solution
乍一看这数据这么小，直接乱$Hash$就好了。
我的$Hash$是$dfs$每个子节点的$val$排序一遍然后$\times {base}^i$。
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include<bits/stdc++.h> using namespace std; #define re register #define mod 19260817 #define int long long class Quick_Input_Output{ private: static const int S=1<<21; #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++) char Rd[S],*A,*B; #define pc putchar public: #undef gc #define gc getchar inline int read(){ int res=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc(); return res*f; } inline void write(int x){ if(x<0) pc('-'),x=-x; if(x<10) pc(x+'0'); else write(x/10),pc(x%10+'0'); } #undef gc #undef pc }I; class Solve{ private: int m,n,fir[55],nxt[55*2],son[55*2],tot,ans[55][55],put[55]; public: inline void add(int x,int y){ ++tot; nxt[tot]=fir[x]; fir[x]=tot; son[tot]=y; } inline int DFS(int x,int fa){ int sum=1; vector<int> v;v.clear(); for(int to,i=fir[x];i;i=nxt[i]){ to=son[i]; if(to==fa) continue ; int tmp=DFS(to,x); v.push_back(tmp); } sort(v.begin(),v.end()); int base=233; for(vector<int>::iterator i=v.begin();i!=v.end();i++){ sum+=(*i)*base%mod;sum%=mod; base*=233;base%=mod; } return sum; } inline void init(){ m=I.read(); for(int i=1;i<=m;i++){ n=I.read(); memset(fir,0,sizeof(fir));tot=0; for(int x,j=1;j<=n;j++){ x=I.read(); if(x==0) continue ; add(x,j);add(j,x); } ans[i][0]=n; for(int j=1;j<=n;j++){ ans[i][j]=DFS(j,0); } sort(ans[i]+1,ans[i]+n+1); put[i]=i; for(int j=1;j<i;j++){ if(ans[i][0]==ans[j][0]){ int ff=0; for(int k=1;k<=n;k++){ if(ans[j][k]==ans[i][k]) ; else{ ff=1; break ; } } if(ff==0){ put[i]=put[j]; break ; } } } } for(int i=1;i<=m;i++) cout<<put[i]<<endl; } }S; signed main(){S.init();} |
