题意
题目链接
Sol
树的同构问题，直接拿hash判一下，具体流程大概是这样的：
首先转化为有根树，预处理出第(i)棵树以(j)为根时的hash值。
那么两个树同构当且仅当把两棵树的hash数组排完序后完全一致(感性理解一下)
代码语言：javascript复制/*
*/
#include<bits/stdc .h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long
#define ull unsigned long long
using namespace std;
const int MAXN = 51, mod = 1e9 7;
const ull base = 997;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, ha[MAXN][MAXN], fa[MAXN], ans[MAXN], top, num[MAXN];
ull st[MAXN], f[MAXN];
vector<int> v[MAXN];
ull dfs(int x, int fa) {
vector<int> st;
f[x] = 1;
for(int i = 0; i < v[x].size(); i ) {
int to = v[x][i];
if(to == fa) continue;
st.push_back(dfs(to, x));
}
sort(st.begin(), st.end());
for(int i = 0; i < st.size(); i ) f[x] = base * f[x] st[i];
return f[x];
}
bool check(int a, int b) {
if(num[a] != num[b]) return 0;
for(int i = 1; i <= num[a]; i )
if(ha[a][i] != ha[b][i]) return 0;
return 1;
}
signed main() {
N = read();
for(int i = 1; i <= N; i ) {
num[i] = read();
for(int j = 1; j <= num[i]; j ) v[j].clear();
for(int j = 1; j <= num[i]; j ) {
fa[j] = read();
if(fa[j]) v[fa[j]].push_back(j), v[j].push_back(fa[j]);
}
for(int j = 1; j <= num[i]; j )
ha[i][j] = dfs(j, 0);
sort(ha[i] 1, ha[i] num[i] 1);
}
for(int i = 1; i <= N; i ) {
ans[i] = i;
for(int j = 1; j <= i - 1; j )
if(check(j, i)) {ans[i] = j; break;}
}
for(int i = 1; i <= N; i ) printf("%dn", ans[i]);
return 0;
}
/*
4
4 2 0 2 3
4 0 1 1 2
4 0 1 1 1
4 0 1 2 3
*/
