Pruefer Code
(tree/pruefer-code.hpp)
Depends on
Verified with
Code
#pragma once
#include "../misc/rng.hpp"
// input: [c \in [0, n)] * (n-2), n>=3
vector<vector<int>> pruefer_code(const vector<int>& code) {
int n = code.size() + 2;
assert(n > 2);
vector<vector<int>> g(n);
vector<int> deg(n, 1);
int e = 0;
for (auto& x : code) deg[x]++;
set<int> ps;
for (int j = 0; j < n; j++) {
if (deg[j] == 1) ps.insert(j);
}
for (auto& i : code) {
if (ps.empty()) break;
int j = *begin(ps);
ps.erase(j);
g[i].push_back(j);
g[j].push_back(i);
if (deg[i] == 1) ps.erase(i);
deg[i]--, deg[j]--;
if (deg[i] == 1) ps.insert(i);
e++;
}
int u = -1, v = -1;
for (int i = 0; i < n; i++) {
if (deg[i] == 1) (u == -1 ? u : v) = i;
}
assert(u != -1 and v != -1);
g[u].push_back(v);
g[v].push_back(u);
e++;
assert(e == n - 1);
return g;
}
vector<vector<int>> random_tree(int n) {
if (n <= 2) {
vector<vector<int>> g(n);
if (n == 2) {
g[0].push_back(1);
g[1].push_back(0);
}
return g;
}
vector<int> pruefer(n - 2);
for (auto& x : pruefer) x = randint(0, n);
return pruefer_code(pruefer);
}
/**
* @brief Pruefer Code
*/
#line 2 "tree/pruefer-code.hpp"
#line 2 "misc/rng.hpp"
#line 2 "internal/internal-seed.hpp"
#include <chrono>
using namespace std;
namespace internal {
unsigned long long non_deterministic_seed() {
unsigned long long m =
chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count();
m ^= 9845834732710364265uLL;
m ^= m << 24, m ^= m >> 31, m ^= m << 35;
return m;
}
unsigned long long deterministic_seed() { return 88172645463325252UL; }
// 64 bit の seed 値を生成 (手元では seed 固定)
// 連続で呼び出すと同じ値が何度も返ってくるので注意
// #define RANDOMIZED_SEED するとシードがランダムになる
unsigned long long seed() {
#if defined(NyaanLocal) && !defined(RANDOMIZED_SEED)
return deterministic_seed();
#else
return non_deterministic_seed();
#endif
}
} // namespace internal
#line 4 "misc/rng.hpp"
namespace my_rand {
using i64 = long long;
using u64 = unsigned long long;
// [0, 2^64 - 1)
u64 rng() {
static u64 _x = internal::seed();
return _x ^= _x << 7, _x ^= _x >> 9;
}
// [l, r]
i64 rng(i64 l, i64 r) {
assert(l <= r);
return l + rng() % u64(r - l + 1);
}
// [l, r)
i64 randint(i64 l, i64 r) {
assert(l < r);
return l + rng() % u64(r - l);
}
// choose n numbers from [l, r) without overlapping
vector<i64> randset(i64 l, i64 r, i64 n) {
assert(l <= r && n <= r - l);
unordered_set<i64> s;
for (i64 i = n; i; --i) {
i64 m = randint(l, r + 1 - i);
if (s.find(m) != s.end()) m = r - i;
s.insert(m);
}
vector<i64> ret;
for (auto& x : s) ret.push_back(x);
sort(begin(ret), end(ret));
return ret;
}
// [0.0, 1.0)
double rnd() { return rng() * 5.42101086242752217004e-20; }
// [l, r)
double rnd(double l, double r) {
assert(l < r);
return l + rnd() * (r - l);
}
template <typename T>
void randshf(vector<T>& v) {
int n = v.size();
for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]);
}
} // namespace my_rand
using my_rand::randint;
using my_rand::randset;
using my_rand::randshf;
using my_rand::rnd;
using my_rand::rng;
#line 4 "tree/pruefer-code.hpp"
// input: [c \in [0, n)] * (n-2), n>=3
vector<vector<int>> pruefer_code(const vector<int>& code) {
int n = code.size() + 2;
assert(n > 2);
vector<vector<int>> g(n);
vector<int> deg(n, 1);
int e = 0;
for (auto& x : code) deg[x]++;
set<int> ps;
for (int j = 0; j < n; j++) {
if (deg[j] == 1) ps.insert(j);
}
for (auto& i : code) {
if (ps.empty()) break;
int j = *begin(ps);
ps.erase(j);
g[i].push_back(j);
g[j].push_back(i);
if (deg[i] == 1) ps.erase(i);
deg[i]--, deg[j]--;
if (deg[i] == 1) ps.insert(i);
e++;
}
int u = -1, v = -1;
for (int i = 0; i < n; i++) {
if (deg[i] == 1) (u == -1 ? u : v) = i;
}
assert(u != -1 and v != -1);
g[u].push_back(v);
g[v].push_back(u);
e++;
assert(e == n - 1);
return g;
}
vector<vector<int>> random_tree(int n) {
if (n <= 2) {
vector<vector<int>> g(n);
if (n == 2) {
g[0].push_back(1);
g[1].push_back(0);
}
return g;
}
vector<int> pruefer(n - 2);
for (auto& x : pruefer) x = randint(0, n);
return pruefer_code(pruefer);
}
/**
* @brief Pruefer Code
*/
Back to top page