Pruefer Code
(tree/pruefer-code.hpp)

• View this file on GitHub
• Last update: 2024-04-28 09:13:11+09:00
• Include: #include "tree/pruefer-code.hpp"

Depends on

• internal/internal-seed.hpp
• misc/rng.hpp

Verified with

• verify/verify-unit-test/rerooting.test.cpp
• verify/verify-unit-test/tree-path.test.cpp

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