Src/Random/RandomTree.hpp

• View this file on GitHub
• Last update: 2025-09-06 12:13:55+09:00
• Include: #include "Src/Random/RandomTree.hpp"

Depends on

• Src/Random/RandomBalancedParenthesis.hpp
• Src/Random/RandomDistinctArray.hpp
• Src/Random/RandomPermutation.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Src/Random/RandomConnectedGraph.hpp

Code

#pragma once

#include "./RandomPermutation.hpp"
#include "./RandomBalancedParenthesis.hpp"

#include <cassert>
#include <concepts>
#include <utility>
#include <vector>
#include <random>
#include <string>

namespace zawa {

namespace Random {

template <std::integral T>
std::vector<std::pair<T, T>> Tree(usize n, bool verify = true) {
    if (n == 0)
        return {};
    const std::string gen = BalancedParenthesis(n - 1, verify);
    std::vector<T> stk{0};
    usize cur = 1;
    std::vector<std::pair<T, T>> res;
    for (u8 c : gen) {
        if (c == '(') {
            const usize v = cur++;
            res.push_back({stk.back(), v});
            stk.push_back(v);
        }
        else {
            stk.pop_back();
        }
    }
    auto perm = Permutation<usize>(n);
    for (auto& [u, v] : res) {
        u = perm[u];
        v = perm[v];
    }
    if (verify) {
        assert(res.size() == n - 1);
        std::vector<bool> vis(n);
        std::vector<std::vector<T>> g(n);
        for (auto [u, v] : res) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        std::vector<std::pair<T, T>> que{std::pair{0, n + 1}};
        for (usize t = 0 ; t < que.size() ; t++) {
            auto [v, p] = que[t];
            for (T x : g[v])
                if (x != p) {
                    assert(!vis[x]);
                    vis[x] = 1;
                    que.push_back({x, v});
                }
        } 
    }
    return res;
}

} // namespace Random

} // namespace zawa

#line 2 "Src/Random/RandomTree.hpp"

#line 2 "Src/Random/RandomPermutation.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Random/RandomPermutation.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <numeric>
#include <vector>
#include <random>

namespace zawa {

namespace Random {

// [0 .. n)
template <std::integral T>
std::vector<T> Permutation(usize n) {
    std::mt19937_64 mt{std::random_device{}()};
    std::vector<T> res(n);
    std::iota(res.begin(), res.end(), T{0});
    std::ranges::shuffle(res, mt);
    return res;
}

} // namespace Random

} // namespace zawa
#line 2 "Src/Random/RandomBalancedParenthesis.hpp"

#line 2 "Src/Random/RandomDistinctArray.hpp"

#line 4 "Src/Random/RandomDistinctArray.hpp"

#line 10 "Src/Random/RandomDistinctArray.hpp"
#include <unordered_map>
#include <unordered_set>

#include <iostream>

namespace zawa {

namespace Random {

template <std::integral T>
std::vector<T> DistinctArray(usize n, T min, T max, bool verify = true) {
    assert(min <= max);
    assert(n <= static_cast<usize>(max - min + 1));
    std::mt19937_64 mt{std::random_device{}()};
    std::vector<T> res(n);
    std::unordered_map<T, T> mp;
    for (T& v : res) {
        T val = static_cast<T>(mt() % (max - min + 1)) + min;
        T replace = [&]() {
            auto it = mp.find(max);
            return it == mp.end() ? max : it->second;
        }();
        auto it = mp.find(val);
        if (it == mp.end()) {
            v = val;
            mp[val] = replace;
        }
        else {
            v = it->second;
            it->second = replace;
        }
        max--;
    }
    if (verify) {
        assert(std::ranges::all_of(res, [&](T v) { return min <= v and v <= static_cast<T>(max + n); }));
        assert(std::unordered_set<T>(res.begin(), res.end()).size() == n);
    }
    return res;
}

} // namespace Random

} // namespace zawa
#line 4 "Src/Random/RandomBalancedParenthesis.hpp"

#line 9 "Src/Random/RandomBalancedParenthesis.hpp"
#include <string>

namespace zawa {

namespace Random {

// https://codeforces.com/blog/entry/103245
std::string BalancedParenthesis(usize n, bool verify = true) {
    if (n == 0)
        return "";
    auto left = DistinctArray<usize>(n, 0, 2 * n, verify);
    std::string gen(2 * n + 1, ')');
    for (usize i : left)
        gen[i] = '(';
    std::vector<i32> pref(gen.size());
    pref[0] = gen[0] == '(' ? +1 : -1;
    for (usize i = 1 ; i < pref.size() ; i++)
        pref[i] = pref[i - 1] + (gen[i] == '(' ? +1 : -1);
    auto sp = std::ranges::min_element(pref) - pref.begin();
    std::string res(2 * n, '(');
    for (usize i = 0 ; i < 2 * n ; i++)
        res[i] = gen[(sp + 1 + i) % gen.size()];
    if (verify) {
        i32 bal = 0;
        for (u8 c : res) {
            assert(c == '(' or c == ')');
            bal += c == '(' ? +1 : -1;
            assert(bal >= 0);
        }
        assert(bal == 0);
    }
    return res;
}

} // namespace Random

} // namespace zawa
#line 5 "Src/Random/RandomTree.hpp"

#line 8 "Src/Random/RandomTree.hpp"
#include <utility>
#line 12 "Src/Random/RandomTree.hpp"

namespace zawa {

namespace Random {

template <std::integral T>
std::vector<std::pair<T, T>> Tree(usize n, bool verify = true) {
    if (n == 0)
        return {};
    const std::string gen = BalancedParenthesis(n - 1, verify);
    std::vector<T> stk{0};
    usize cur = 1;
    std::vector<std::pair<T, T>> res;
    for (u8 c : gen) {
        if (c == '(') {
            const usize v = cur++;
            res.push_back({stk.back(), v});
            stk.push_back(v);
        }
        else {
            stk.pop_back();
        }
    }
    auto perm = Permutation<usize>(n);
    for (auto& [u, v] : res) {
        u = perm[u];
        v = perm[v];
    }
    if (verify) {
        assert(res.size() == n - 1);
        std::vector<bool> vis(n);
        std::vector<std::vector<T>> g(n);
        for (auto [u, v] : res) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        std::vector<std::pair<T, T>> que{std::pair{0, n + 1}};
        for (usize t = 0 ; t < que.size() ; t++) {
            auto [v, p] = que[t];
            for (T x : g[v])
                if (x != p) {
                    assert(!vis[x]);
                    vis[x] = 1;
                    que.push_back({x, v});
                }
        } 
    }
    return res;
}

} // namespace Random

} // namespace zawa

Back to top page