tree/process-of-merging-tree.hpp

• View this file on GitHub
• Last update: 2022-08-22 19:46:43+09:00
• Include: #include "tree/process-of-merging-tree.hpp"

Code

#pragma once

// マージ過程を表す木
// es の昇順に木をマージしていく。(es にはマージに使わない辺が入っていてよい)
//
// 返り値 : (graph, 補助的な頂点に対応する辺の重み, root)
template <typename T>
tuple<WeightedGraph<T>, vector<T>, int> process_of_merging_tree(
    const Edges<T>& es) {
  int n = 1;
  for (auto& e : es) n = max(n, max(e.src, e.to) + 1);
 
  WeightedGraph<T> g(n * 2 - 1);
  vector<T> nodes(n - 1);
 
  UnionFind uf(n);
  vector<int> roots(n);
  iota(begin(roots), end(roots), 0);
  int aux = n;
 
  for (auto& e : es) {
    int u = e.src, v = e.to;
    if (uf.same(u, v)) continue;
    T w = e.cost;
    auto f = [&](int x, int y) {
      g[aux].emplace_back(aux, roots[x], w);
      g[aux].emplace_back(aux, roots[y], w);
      roots[x] = roots[y] = aux;
    };
    uf.unite(u, v, f);
    nodes[aux - n] = w;
    aux++;
  }
  assert(aux == 2 * n - 1);
 
  return {g, nodes, 2 * n - 2};
}

#line 2 "tree/process-of-merging-tree.hpp"

// マージ過程を表す木
// es の昇順に木をマージしていく。(es にはマージに使わない辺が入っていてよい)
//
// 返り値 : (graph, 補助的な頂点に対応する辺の重み, root)
template <typename T>
tuple<WeightedGraph<T>, vector<T>, int> process_of_merging_tree(
    const Edges<T>& es) {
  int n = 1;
  for (auto& e : es) n = max(n, max(e.src, e.to) + 1);
 
  WeightedGraph<T> g(n * 2 - 1);
  vector<T> nodes(n - 1);
 
  UnionFind uf(n);
  vector<int> roots(n);
  iota(begin(roots), end(roots), 0);
  int aux = n;
 
  for (auto& e : es) {
    int u = e.src, v = e.to;
    if (uf.same(u, v)) continue;
    T w = e.cost;
    auto f = [&](int x, int y) {
      g[aux].emplace_back(aux, roots[x], w);
      g[aux].emplace_back(aux, roots[y], w);
      roots[x] = roots[y] = aux;
    };
    uf.unite(u, v, f);
    nodes[aux - n] = w;
    aux++;
  }
  assert(aux == 2 * n - 1);
 
  return {g, nodes, 2 * n - 2};
}

Back to top page