test/unit/subtree_classify.test.cpp

• View this file on GitHub
• Last update: 2026-10-27 06:10:50+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

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

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <vector>

#include "graph/subtree_classify.hpp"
// AHU canonical string of the subtree rooted at u
std::string canon(const std::vector<std::vector<int>>& ch, int u) {
    std::vector<std::string> s;
    for (int v : ch[u]) s.push_back(canon(ch, v));
    std::sort(s.begin(), s.end());
    std::string res = "(";
    for (auto& t : s) res += t;
    return res + ")";
}
void check(const std::vector<int>& a, const std::vector<std::vector<int>>& ch, int root) {
    int n = int(ch.size());
    std::vector<std::string> c(n);
    std::vector<int> order{root};
    for (int i = 0; i < int(order.size()); i++)
        for (int v : ch[order[i]]) order.push_back(v);
    for (int u : order) c[u] = canon(ch, u);
    std::map<std::string, int> cls;
    for (int u = 0; u < n; u++) cls.emplace(c[u], 0);
    int k = int(cls.size());
    assert(*std::max_element(a.begin(), a.end()) == k - 1);
    assert(*std::min_element(a.begin(), a.end()) == 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) assert((a[i] == a[j]) == (c[i] == c[j]));
}
int main() {
    std::mt19937 rng(20261027);
    for (int iter = 0; iter < 3000; iter++) {
        int n = 1 + rng() % 9;
        int root = rng() % n;
        // random labelled tree via random parent in a random order
        std::vector<int> perm(n);
        for (int i = 0; i < n; i++) perm[i] = i;
        std::shuffle(perm.begin(), perm.end(), rng);
        std::swap(perm[0], *std::find(perm.begin(), perm.end(), root));
        std::vector<std::vector<int>> ch(n), und(n);
        for (int i = 1; i < n; i++) {
            int p = perm[rng() % i], v = perm[i];
            ch[p].push_back(v);
            und[p].push_back(v);
            und[v].push_back(p);
        }
        for (auto& l : und) std::shuffle(l.begin(), l.end(), rng);
        std::vector<int> a = subtree_classify(ch, root);
        check(a, ch, root);
        check(subtree_classify(und, root), ch, root);
    }
    {
        // path of length 2e5: no recursion depth issue
        int n = 200000;
        std::vector<std::vector<int>> g(n);
        for (int i = 1; i < n; i++) {
            g[i - 1].push_back(i);
            g[i].push_back(i - 1);
        }
        std::vector<int> a = subtree_classify(g);
        for (int i = 0; i < n; i++) assert(a[i] == n - 1 - i);
    }
    {
        // star: all leaves in one class
        int n = 100000;
        std::vector<std::vector<int>> g(n);
        for (int i = 1; i < n; i++) g[0].push_back(i);
        std::vector<int> a = subtree_classify(g);
        assert(a[0] == 1);
        for (int i = 1; i < n; i++) assert(a[i] == 0);
    }
    {
        std::vector<int> a = subtree_classify(std::vector<std::vector<int>>(1));
        assert((a == std::vector<int>{0}));
    }
    std::cout << "Hello World" << std::endl;
}

#line 1 "test/unit/subtree_classify.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <vector>

#line 6 "graph/subtree_classify.hpp"
std::vector<int> subtree_classify(const std::vector<std::vector<int>>& g, int root = 0) {
    int n = int(g.size());
    assert(0 <= root && root < n);
    std::vector<int> par(n, -1), order;
    order.reserve(n);
    order.push_back(root);
    par[root] = root;
    for (int i = 0; i < int(order.size()); i++) {
        int u = order[i];
        for (int v : g[u]) {
            if (v == par[u]) continue;
            assert(par[v] == -1);
            par[v] = u;
            order.push_back(v);
        }
    }
    assert(int(order.size()) == n);
    std::vector<int> ret(n);
    std::map<std::vector<int>, int> id;
    std::vector<int> key;
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        key.clear();
        for (int v : g[u]) {
            if (v != par[u]) key.push_back(ret[v]);
        }
        std::sort(key.begin(), key.end());
        ret[u] = id.try_emplace(key, int(id.size())).first->second;
    }
    return ret;
}
#line 11 "test/unit/subtree_classify.test.cpp"
// AHU canonical string of the subtree rooted at u
std::string canon(const std::vector<std::vector<int>>& ch, int u) {
    std::vector<std::string> s;
    for (int v : ch[u]) s.push_back(canon(ch, v));
    std::sort(s.begin(), s.end());
    std::string res = "(";
    for (auto& t : s) res += t;
    return res + ")";
}
void check(const std::vector<int>& a, const std::vector<std::vector<int>>& ch, int root) {
    int n = int(ch.size());
    std::vector<std::string> c(n);
    std::vector<int> order{root};
    for (int i = 0; i < int(order.size()); i++)
        for (int v : ch[order[i]]) order.push_back(v);
    for (int u : order) c[u] = canon(ch, u);
    std::map<std::string, int> cls;
    for (int u = 0; u < n; u++) cls.emplace(c[u], 0);
    int k = int(cls.size());
    assert(*std::max_element(a.begin(), a.end()) == k - 1);
    assert(*std::min_element(a.begin(), a.end()) == 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) assert((a[i] == a[j]) == (c[i] == c[j]));
}
int main() {
    std::mt19937 rng(20261027);
    for (int iter = 0; iter < 3000; iter++) {
        int n = 1 + rng() % 9;
        int root = rng() % n;
        // random labelled tree via random parent in a random order
        std::vector<int> perm(n);
        for (int i = 0; i < n; i++) perm[i] = i;
        std::shuffle(perm.begin(), perm.end(), rng);
        std::swap(perm[0], *std::find(perm.begin(), perm.end(), root));
        std::vector<std::vector<int>> ch(n), und(n);
        for (int i = 1; i < n; i++) {
            int p = perm[rng() % i], v = perm[i];
            ch[p].push_back(v);
            und[p].push_back(v);
            und[v].push_back(p);
        }
        for (auto& l : und) std::shuffle(l.begin(), l.end(), rng);
        std::vector<int> a = subtree_classify(ch, root);
        check(a, ch, root);
        check(subtree_classify(und, root), ch, root);
    }
    {
        // path of length 2e5: no recursion depth issue
        int n = 200000;
        std::vector<std::vector<int>> g(n);
        for (int i = 1; i < n; i++) {
            g[i - 1].push_back(i);
            g[i].push_back(i - 1);
        }
        std::vector<int> a = subtree_classify(g);
        for (int i = 0; i < n; i++) assert(a[i] == n - 1 - i);
    }
    {
        // star: all leaves in one class
        int n = 100000;
        std::vector<std::vector<int>> g(n);
        for (int i = 1; i < n; i++) g[0].push_back(i);
        std::vector<int> a = subtree_classify(g);
        assert(a[0] == 1);
        for (int i = 1; i < n; i++) assert(a[i] == 0);
    }
    {
        std::vector<int> a = subtree_classify(std::vector<std::vector<int>>(1));
        assert((a == std::vector<int>{0}));
    }
    std::cout << "Hello World" << std::endl;
}

Back to top page