根付き木の同型性による部分木の分類
(graph/subtree_classify.hpp)

• View this file on GitHub
• Last update: 2023-01-11 14:05:50+09:00
• Include: #include "graph/subtree_classify.hpp"

概要

• $N$ 頂点の根付き木について、ある頂点を根とする（全部で $N$ 個の）部分木を、根付き木の同型性で分類する。

使い方

• subtree_classify(g, root = 0): 次の条件を満たす整数列 a を求める。
  • 部分木の種類数を $K$ としたとき、$0\leq a_i \lt K$
  • 頂点 i、 頂点 j を根とする部分木が同型 $\iff$ $a_i = a_j$

計算量

• $\mathcal{O}(N \log N)$

Verified with

• test/library-checker/rooted_tree_isomorphism_classification.test.cpp

Code

#pragma once

#include <algorithm>
#include <map>
#include <vector>
std::vector<int> subtree_classify(std::vector<std::vector<int>> g,
                                  int root = 0) {
    std::vector<int> ret(g.size());
    std::map<std::vector<int>, int> cache;
    auto dfs = [&](auto dfs, int u) -> int {
        std::vector<int> hash;
        hash.push_back(-1);
        for (int v : g[u]) hash.push_back(dfs(dfs, v));
        std::sort(hash.begin(), hash.end());
        hash.push_back(-1);
        if (!cache.count(hash)) cache[hash] = int(cache.size());
        return ret[u] = cache[hash];
    };
    dfs(dfs, root);
    return ret;
}

#line 2 "graph/subtree_classify.hpp"

#include <algorithm>
#include <map>
#include <vector>
std::vector<int> subtree_classify(std::vector<std::vector<int>> g,
                                  int root = 0) {
    std::vector<int> ret(g.size());
    std::map<std::vector<int>, int> cache;
    auto dfs = [&](auto dfs, int u) -> int {
        std::vector<int> hash;
        hash.push_back(-1);
        for (int v : g[u]) hash.push_back(dfs(dfs, v));
        std::sort(hash.begin(), hash.end());
        hash.push_back(-1);
        if (!cache.count(hash)) cache[hash] = int(cache.size());
        return ret[u] = cache[hash];
    };
    dfs(dfs, root);
    return ret;
}

Back to top page