Menu
Article ACM

树的同构 ( 附带 POJ 1635 )

NodeKey

NodeKey

• 3 min read

前言

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专题。

Share