ラベル付き木から prüfer sequence（プリューファ列）と呼ばれる整数列への一対一対応を説明します．
Prüfer sequence
各ラベル付き木に対して Prüfer sequence と呼ばれる整数列が一対一対応します．まず初めにラベル付き木から Prüfer sequence への変換方法を示して，その後で Prüfer sequence からラベル付き木への逆変換を示します．
Prüfer sequence 👉 ラベル付き木
次に長さ 
の prüfer sequence 
から頂点数 
のラベル付き木 
への変換を説明します．各頂点 
に対して，
での 
の出現回数に1を足した値は の次数に等しくなります．疑似コードど C++のソースコードを下に載せます．C++の実行時間は 
です．
この変換は上の変換の逆変換となるので，これらの変換は一対一対応となります．
1. 
を頂点
の次数を
とする
2. 
から
まで次を繰り返す
2-1. 
となるラベル最小の頂点
を求める
2-2. 頂点
と
の間に辺を加える
2-3. 
と
の値を1減らす
3. 
となる頂点
と
の間に辺を加える
#include <iostream>
#include <vector>
#include <queue>
struct Graph {
size_t n;
std::vector<std::vector<int>> adj;
Graph(size_t _n) : n(_n), adj(_n) {}
void add_edge(const int u, const int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
};
Graph PruferSequenceToTree(const std::vector<int> seq) {
const int n = seq.size() + 2;
std::vector<int> deg(n, 1);
for (const int v : seq) ++deg[v];
std::priority_queue<int, std::vector<int>, std::greater<int>> que;
for (int v = 0; v < n; ++v) if (deg[v] == 1) que.push(v);
Graph tree(n);
for (const int v : seq) {
const int u = que.top(); que.pop();
tree.add_edge(v, u);
--deg[v]; --deg[u];
if (deg[v] == 1) que.push(v);
}
const int lst = que.top(); que.pop();
tree.add_edge(lst, que.top());
return tree;
}
int main() {
std::cin.tie(0); std::ios::sync_with_stdio(false);
int size;
std::cin >> size;
std::vector<int> prufer_sequence(size);
for (auto &&v : prufer_sequence) std::cin >> v;
auto tree = PruferSequenceToTree(prufer_sequence);
std::cout << "#vertices: " << tree.n << '\n';
for (size_t v = 0; v < tree.n; ++v) {
std::cout << v << ": ";
for (auto u : tree.adj[v]) std::cout << u << " ";
std::cout << '\n';
}
return 0;
}
のラベル付き木
