题目链接

bzoj4337: BJOI2015 树的同构

题解

树哈希的一种方法

对于每各节点的哈希值为hash[x] = hash[sonk[x]] * p[k];

p为素数表

代码

#include<cstdio>

#include<cstring>

#include<algorithm> 

inline int read() {

    int x = 0,f = 1;

    char c  = getchar() ;

    while(c < '0' || c > '9')c = getchar();

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

    return x * f;

}

const int maxn = 3007;

unsigned int hash[maxn][maxn];

unsigned int p[]={0,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317};

unsigned int f[maxn];

int m;

struct node {

    int v,next;

}  edge[maxn << 1];

int num = 0;

int head[maxn];

inline void add_edge(int u,int v) {edge[++ num].v = v; edge[num].next = head[u];head[u] = num;}

void dfs(int x,int fa) {

    int num = 0;

    unsigned int son[107];

    son[++ num] = 1;

    for(int i = head[x];i;i = edge[i].next) {

        int v = edge[i].v;

        if(v == fa) continue;

        dfs(v,x);

        son[++ num] = f[v];

    }

    std::sort(son + 1, son + num + 1);

    f[x] = 0;

    for(int i = 1;i <= num;++ i) f[x] += p[i] * son[i];

}

int main() {

    m = read();

    int n;

    for(int i = 1;i <= m;++ i) {

        memset(head,0,sizeof head); num = 0;

        n = read();

        for(int x,j = 1;j <= n;++ j) {

            x = read(); if(x) { add_edge(x,j),add_edge(j,x); }

        }

        for(int j = 1;j <= n;++ j) { dfs(j,0),hash[i][j] = f[j];}

        std::sort(hash[i] + 1,hash[i] + n + 1);

        for(int j = 1;j <= i;++ j) {

            int k;

            for(k = 1;k <= n;++ k)

                if(hash[j][k] != hash[i][k]) break;

            if(k > n) {printf("%d\n",j);break; }

        }

    }

    return 0;

}