Prüfer-526互联

入门

长度为 \(n - 2\) 的双射，可以构建起数列和无根树的关系。

构建方法：

取 \(\text index\) 最小的叶子，向 Prüfer 加入其父亲，并删除其本身。

大概是非常容易写 \(n \log n\) 的小根堆即可。

摘自 OI-wiki :

vector<vector<int>> adj;

vector<int> pruefer_code() {
  int n = adj.size();
  set<int> leafs;
  vector<int> degree(n);
  vector<bool> killed(n, false);
  for (int i = 0; i < n; i++) {
    degree[i] = adj[i].size();
    if (degree[i] == 1) leafs.insert(i);
  }

  vector<int> code(n - 2);
  for (int i = 0; i < n - 2; i++) {
    int leaf = *leafs.begin();
    leafs.erase(leafs.begin());
    killed[leaf] = true;
    int v;
    for (int u : adj[leaf])
      if (!killed[u]) v = u;
    code[i] = v;
    if (--degree[v] == 1) leafs.insert(v);
  }
  return code;
}

但是其实可以做到线性构造。

vector<vector<int>> adj;
vector<int> parent;

void dfs(int v) {
  for (int u : adj[v]) {
    if (u != parent[v]) parent[u] = v, dfs(u);
  }
}

vector<int> pruefer_code() {
  int n = adj.size();
  parent.resize(n), parent[n - 1] = -1;
  dfs(n - 1);

  int ptr = -1;
  vector<int> degree(n);
  for (int i = 0; i < n; i++) {
    degree[i] = adj[i].size();
    if (degree[i] == 1 && ptr == -1) ptr = i;
  }

  vector<int> code(n - 2);
  int leaf = ptr;
  for (int i = 0; i < n - 2; i++) {
    int next = parent[leaf];
    code[i] = next;
    if (--degree[next] == 1 && next < ptr) {
      leaf = next;
    } else {
      ptr++;
      while (degree[ptr] != 1) ptr++;
      leaf = ptr;
    }
  }
  return code;
}

大概是考虑暴力删除所有叶子，然后看看父亲行不行。那时间复杂度怎么保证？这个程序是先逐次删除所有叶子节点，那么可以考虑在过程中父亲若 \(\text index\) 较小，那必然会提前删除，否则会留到后面删，故可以保证只会遍历到每一个节点的父亲边到一次，故为 \(O(n)\)。

重构树

那么我们可以考虑先求出 \(\text deg_i\) 那么我们可以找度数为 1 意义下的 \(\text index\) 最小，然后连到 Prüfer 上面即可。

这个可以用小根堆维护，但也有线性方法, 方法大致和上面差不多，直接塴了 OI-wiki 了。

vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
  int n = code.size() + 2;
  vector<int> degree(n, 1);
  for (int i : code) degree[i]++;

  int ptr = 0;
  while (degree[ptr] != 1) ptr++;
  int leaf = ptr;

  vector<pair<int, int>> edges;
  for (int v : code) {
    edges.emplace_back(leaf, v);
    if (--degree[v] == 1 && v < ptr) {
      leaf = v;
    } else {
      ptr++;
      while (degree[ptr] != 1) ptr++;
      leaf = ptr;
    }
  }
  edges.emplace_back(leaf, n - 1);
  return edges;
}