1. 作用
判断一些树是否同构。
2. 方法
2.1. 具体操作
这类方法需要一个多重集的哈希函数。以某个结点为根的子树的哈希值,就是以它的所有儿子为根的子树的哈希值构成的多重集的哈希值,即:
\[h_u=f(\{h_v|v\in son(u) \}) \]其中\(h_x\)表示以\(x\)为根的子树的哈希值,\(f\)是多重集的哈希函数
以代码中运用的哈希方法为例,式子是:
\[h_u=(1+\sum_{v\in son(u)} g(h_v)) \bmod p \]其中,g(i)表示整数到整数的映射,说人话就是一种运算,将一个整数转化为另一个整数
2.2. 代码
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n,head[1000005],edgenum;
struct edge{
int to,nxt;
}e[2000005];
void add_edge(int u,int v)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
head[u]=edgenum;
}
ull mask;
ull get_hash(ull x)
{
x^=mask;
x^=x<<13;
x^=x>>7;
x^=x<<17;
x^=mask;
return x;
}
ull h[1000005];
set<ull> tr;
void dfs(int u,int fa)
{
h[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
h[u]+=get_hash(h[v]);
}
tr.insert(h[u]);
}
int main()
{
srand((unsigned)time(0));
mask=1ll*rand()*rand();
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs(1,0);
printf("%d",tr.size());
return 0;
}
2.3. 正确性证明
每次前后各异或一次mask,其实相当于一种加密和解密的过程,第一次是解密,第二次是加密
每一次get_hash运算,都是对解密后的数字进行处理,所以最后的得数都是与mask进行一次异或运算的结果
因为求解方法是相加,所以若两棵树同构,经过运算后数的和必然相同
标签:head,ull,int,mask,笔记,学习,edgenum,哈希 From: https://www.cnblogs.com/wangsiqi2010916/p/18102718