洛谷5043 树同构

树哈希。

考虑一种树哈希算法，给树指定一个根，对于每个点，把子节点的哈希值排序，然后写成seed进制数，最后+1然后乘seed2.

这样既考虑了结构的影响又考虑了深度的影响。

对于每个点均做根哈希一遍，最后每个树可以得到一个哈希集合，比较两个树的哈希集合是否相等即可。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <set>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;
const int_t BASE = 1023;
const int_t seed = 233;
const int_t mod = 998244353;
int_t power(int_t base, int_t index)
{
    int_t result = 1;
    while (index)
    {
        if (index & 1)
            result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}

int_t result[101];
std::set<int_t> hashes[101];
std::vector<int_t> graph[101];
int_t parent[101];
int_t find(int_t x)
{
    if (parent[x] == x)
        return x;
    return parent[x] = find(parent[x]);
}
int_t DFS(int_t vtx, int_t from = -1)
{
    std::vector<int_t> chds;
    for (int_t to : graph[vtx])
    {
        if (to == from)
            continue;
        chds.push_back(DFS(to, vtx));
    }
    std::sort(chds.begin(), chds.end());
    int_t sum = 0;
    for (int_t x : chds)
    {
        sum = (sum * seed + x) % mod;
    }
    return (sum + 1) * BASE % mod;
}

int main()
{
    int_t m;
    cin >> m;
    for (int_t _ = 1; _ <= m; _++)
    {
        parent[_] = _;
        int_t n;
        cin >> n;
        for (int_t i = 1; i <= n; i++)
            graph[i].resize(0);
        for (int_t i = 1; i <= n; i++)
        {
            int_t parent;
            cin >> parent;
            if (parent)
            {
                graph[i].push_back(parent);
                graph[parent].push_back(i);
            }
        }
        for (int_t i = 1; i <= n; i++)
        {
            int_t x = DFS(i);
            hashes[_].insert(x);
        }
    }
    for (int_t i = 1; i <= m; i++)
    {
        for (int_t j = i + 1; j <= m; j++)
        {
            if (hashes[i] == hashes[j])
            {
                parent[find(i)] = find(j);
            }
        }
    }
    static int_t result[101];
    std::map<int_t, std::set<int_t>> groups;
    for (int_t i = 1; i <= m; i++)
    {
        groups[find(i)].insert(i);
    }
    for (const auto &pack : groups)
    {
        for (int_t x : pack.second)
        {
            result[x] = *pack.second.begin();
        }
    }
    for (int_t i = 1; i <= m; i++)
        cout << result[i] << endl;
    return 0;
}