【xsy1319】树的同构 Hash

Hash 题目

题意

树是一种很常见的数据结构。
我们把 $N$ 个点， $N-1$ 条边的连通无向图称为树。
若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。
对于两个树 $T_1$ 和 $T_2$ ，如果能够把树 $T_1$ 的所有点重新标号，使得树 $T_1$ 和树 $T_2$ 完全相
同，那么这两个树是同构的。也就是说，它们具有相同的形态。
现在，给你 $M$ 个有根树，请你把它们按同构关系分成若干个等价类。
$N,M\leq 50$

分析

问两棵树是否同构。
直接判断的复杂度为 $O(2^n)$ ，会TLE的。
所以肯定是用一些比较不同的必然条件来判断。

我们想到了....
Hash！？
考虑构造哈希函数 $H: Tree\rightarrow Z$ ，通过Hash函数快速判断两棵树是否长一样。
怎样有效地设计Hash，刻画两棵树的形态呢？

首先，如果把无根树变成有根树，肯定会好一点。
所以，每棵无根树变成 $n$ 棵有根树，对应 $n$ 个Hash值。
两棵树同构，当且仅当存在至少一个共同的Hash值。

其实也可以从重心的角度出发。
找到重心，把重心和重心周围的一圈作为根，这样可以优化复杂度。

设计的Hash，不能涉及到树的儿子的先后顺序，但要考虑到儿子。
所以怎么设计其实都可以。
我的设计（来自以前的题解）：
$h_u=(a_d+b_d∑h_{son})^2$
其中 $a_d,b_d$ 是随机生成的确定值。

思路梳理

同构，这样的问题在判断是否等于，等于与不等于、是否存在这两种问题，通常用Hash就搞掂了。

要体现树的形态，首先这是一棵无根树，所以要转化为有根树来判断。可以枚举每一个节点作为根，也可以找到重心，并枚举它周围的一圈。

Hash函数的设计，不能体现儿子的先后顺序，但是深度是确定的，对每一个深度确定两个随机值，Hash函数中嵌入随机值和儿子的情况就好了。

这种同构问题，通常的瓶颈在于判断同构的时间过长。
这时候我们就要用当前这个结构的某些象征来进行判断。
常用Hash，或者最小表示法之类的。

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;
#define mp(i,j) make_pair(i,j)
typedef unsigned long long ull;
typedef pair<ull,ull> pint;
const int N=64;
int m;
int n;
struct Edge
{
    int v,nxt;
}mp[N<<1];
int tt,hd[N];
ull h1[2][N];
ull h2[2][N];
map<pint,int> p;
inline int rd(void)
{
    int x=0; char c=getchar();
    for (;!isdigit(c);c=getchar());
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x;
}
inline int add(int u,int v)
{
    mp[++tt].v=v;
    mp[tt].nxt=hd[u];
    hd[u]=tt;
}
ull dfs(int t,int now,int pre,int dep)
{
    ull ret=h1[t][dep];
    for (int k=hd[now];k;k=mp[k].nxt)
        if (mp[k].v!=pre)
            ret+=dfs(t,mp[k].v,now,dep+1)*h2[t][dep];
    return ret*ret;
}
int main(void)
{
//  freopen("c.in","r",stdin);
//  freopen("c.out","w",stdout);
    srand(time(0));
    for (int t=0;t<=1;t++)
        for (int i=1;i<N;i++)
            h1[t][i]=rand(),h2[t][i]=rand();
    int res; m=rd();
    for (int t=1;t<=m;t++)
    {
        res=t;
        tt=0;
        memset(hd,0,sizeof hd);
        int x; n=rd();
        for (int i=1;i<=n;i++)
        {
            x=rd();
            if (x) add(i,x),add(x,i);
        }
        ull d0,d1; pint d;
        for (int rt=1;rt<=n;rt++)
        {
            d0=dfs(0,rt,0,1);
            d1=dfs(1,rt,0,1);
            d=mp(d0,d1);
            if (p[d]==t) continue;
            if (!p[d])
                p[d]=t;
            else res=min(res,p[d]);
        }
        printf("%d\n",res);
    }
    return 0;
}