Menu
Article ACM

BZOJ 4337 树的同构

NodeKey

NodeKey

• 3 min read

昨天的多校有一道需要树Hash的基础，于是就找到了这题。这题应该算得上是树Hash的裸题了。

树Hash的方法其实十分简单。有兴趣的看一下我的这篇 博文
然而上面那片博文是定根结点的，如果根节点固定，对于树的形态进行Hash，实际上是非常简单的。

再次简单说一下树Hash的原理，对于有根树，我们Hash的是树的形态，而树的形态则有每一层的结点个数与结点所连接的相同父亲结点所决定。
因此我们对于同一层的并且是同一个父亲的结点作一个相同的Hash，那么就得到了我们要得答案。

不过也有一个简单也正确的写法，就是将同一层并且具有相同孩子结点数量作同一个Hash，也可得到我们想要的结果。

但上述方法是针对有根树而言，如果不定根，则不好判断。
这是我们可以对小数据选择枚举所有结点，对较大数据选择寻找树的重心(不会超过两个)。

下面放上题解。

2017-8-14更新： 该理论用于有根树已经被推翻，对于无根树，也就是这道题，莫名适用，也许是数据水……

题意：
给你( n ) 棵树，每棵树用给定每个结点的父亲予以表示。问对于每一棵树，与它同构的并且序号最小的是哪一棵。

思路：
数据非常小，只有不到50。我这里用了枚举 而且不也不会找重心
对于第 ( n ) 棵树，它的答案必然小于等于 ( n )。

值得注意的是，这是无根树，( 0 ) 结点不计其中。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

typedef long long ll;

const int maxn = 52;

int m, n;
int father;
int h[maxn][maxn], dep[maxn];

int prime[] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 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
};

int cnt[maxn];
vector<int> G[maxn];
queue<int> que;

int getHash(int root)
{
    memset(dep, 0, sizeof dep);
    int ret = 0, u;
    que.push(root), dep[root] = 1;
    while (!que.empty()) {
        u = que.front(), que.pop();
        ret += G[u].size() * prime[dep[u]];
        int sz = G[u].size();
        for (int i = 0; i < sz; i++) {
            if (!dep[G[u][i]]) {
                que.push(G[u][i]);
                dep[G[u][i]] = dep[u] + 1;
            }
        }
    }
    return ret;
}

int main()
{
    scanf("%d", &m);
    range(k, 1, m)
    {
        scanf("%d", &n);
        cnt[k] = n;
        range(i, 1, n) G[i].clear();
        range(i, 1, n)
        {
            scanf("%d", &father);
            if (father)
                G[father].push_back(i), G[i].push_back(father);
        }
        range(i, 1, n) h[k][i] = getHash(i);
        sort(h[k] + 1, h[k] + n + 1);
        range(i, 1, k) if (cnt[i] == n)
        {
            int j = 1;
            while (j <= n && h[k][j] == h[i][j])
                j++;
            if (j > n) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}
Share