Hash

BZOJ 4337 树的同构

Posted on

昨天的多校有一道需要树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;
}
Hash

树的同构 ( 附带 POJ 1635 )

Posted on

前言

POJ 1635 这是刷字符串的时候被煞笔天海放进来的一道题,题意是让你判断两棵树是否同构。
我想他的主要目的应该是听了肥宅带鱼的B话,把树上的最小表示法也放进来了……
这特么完全不是一个算法好么 虽然可以转化

必要知识 (可跳过

首先我们必须得知道两棵树的同构是如何定义的。
一棵树通过不断交换他的子树位置,最后能够与另一棵树完全相同,则称这两颗树同构。

( 例子我就不举了……

树上的最小表示法

最先看得就是树上的最小表示法,其实树上的最小表示法,并没有什么难的,反而可以说是以中非常暴力的方法。判断同构,非常慢,在这里我并不推荐。

简单说一下原理。
通过dfs找出当前节点的每个子树的序列表示,再对所有子树进行排序,再将排序后的序列相加来作为当前根树的序列表示。

以POJ 1635 为例的代码 570 ms

#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <string>

using namespace std;
const int maxn = 1e6 + 5;

#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))

string treeMinR(int pos, const string& str)
{
    int len = str.length();
    vector<string> vec;
    while (pos < len && str[pos] == '0') {
        vec.push_back('0' + treeMinR(pos + 1, str));
        pos += vec.back().size();
    }
    sort(vec.begin(), vec.end());
    string res = "";
    each(i, (int)vec.size()) res += vec[i];
    return res + '1';
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    string a, b;
    cin >> T;
    while (T--) {
        cin >> a >> b;
        if (treeMinR(0, a) == treeMinR(0, b))
            cout << "same" << endl;
        else
            cout << "different" << endl;
    }
    return 0;
}

Hash 解法

这是杨戈的Hash论文在实际题目的应用,判断树的同构。

首先我们必须认识到,因为两棵同构树只是从一维上的顺序不同而已。如果对于一棵树,我们用一个在我们可允许范围的数字(也就是我们的Hash值)去表示他,那么一个节点的所有子树的Hash值之和,将与子树的顺序毫不相关!!

Hash的神奇与魅力!!!!

以POJ 1635 为例的代码示例 0ms

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;
const int maxn = 5e3 + 5;
const int mod = 11257;

#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))

int val[maxn], len;
char a[maxn], b[maxn], *it;

int Hash(int pos)
{
    int sum = val[pos];
    while (it && *it++ == '0')
        sum = (sum + val[pos] * Hash(pos + 1)) % mod;
    return sum * sum % mod;
}

int main()
{
    each(i, 5000) val[i] = rand() % mod;
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %s", a, b);
        it = a, len = strlen(a);
        int ha = Hash(0);
        it = b, len = strlen(b);
        int hb = Hash(0);
        puts(ha == hb ? "same" : "different");
    }
    return 0;
}

鉴于这等差距,我决定于今日就开启我的Hash专题。