[BJOI2015]树的同构「树Hash」
题目描述
树是一种很常见的数据结构。
我们把 (N) 个点，(N−1) 条边的连通无向图称为树。
若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。
对于两个树 (T_{1}) 和 (T_{2})，如果能够把树 (T_{1}) 的所有点重新标号，使得树 (T_{1}) 和树 (T_{2}) 完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。
现在，给你 (M) 个无根树，请你把它们按同构关系分成若干个等价类。
输入格式
第一行，一个整数 (M)。
接下来 (M) 行，每行包含若干个整数，表示一个树。第一个整数 (N)表示点数。接下来 (N) 个整数，依次表示编号为 (1) 到 (N) 的每个点的父亲结点的编号。根节点父亲结点编号为 (0)。
输出格式
输出 (M) 行，每行一个整数，表示与每个树同构的树的最小编号。
输入输出样例
输入 #1
4
4 0 1 1 2
4 2 0 2 3
4 0 1 1 1
4 0 1 2 3
输出 #1
1
1
3
1
思路分析
没思路
模板题
- 一开始看见这题一脸懵，直到了解了树哈希这个东西->here传送门
- 貌似这个树哈希很容易被Hack，当然这不是关注点
- 树哈希正是用来判断题目中的“树的同构”这一概念的，至于原理应该和字符串哈希类似，
我还没找到一个对原理有详细解释的 - 模板题直接上板子不就好了
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const ll maxn=1001,base = 131;
ll ans[maxn][maxn],n,m,head[maxn],tot,x;
struct edge{
int to,next;
}e[maxn];
void add(int x,int y){
e[++tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
ll hash(int x,int f){//核心代码，bfs遍历子节点
ll q[maxn],ans = maxn,top = 0;
for(int i = head[x];i;i = e[i].next){
if(e[i].to!=f)q[++top] = hash(e[i].to,x);
}
sort(q+1,q+1+top); //必须sort
for(int i = 1;i <= top;i++){
ans = ans*base+q[i]; //计算哈希值
}
return ans*base+maxn+1; //加1！因为还有叶子节点
}
int main(){
m = read();
for(int i = 1;i <= m;i++){
memset(head,0,sizeof(head));
tot = 0;
n = read();
for(int j = 1;j <= n;j++){
x = read();
if(x)add(x,j),add(j,x);
}
for(int j = 1;j <= n;j++)ans[i][j] = hash(j,0);//每个节点作为根节点都跑一遍
sort(ans[i],ans[i]+1+n);//还是必须sort(原来sort还可以想这样只用一维)
for(int j = 1,k = 0;j <= i;j++){//根据哈希值比较是否为同构，这里的操作很简洁巧妙
while(k<=n){//不断对比
if(ans[i][++k]!=ans[j][k])break;
}
if(k>n){//说明对比成功
printf("%d
",j); //j即为与当前的树同构的编号
break;
}
}
}
return 0;
}