根付き木に変換(Convert-Rooted-Tree)

説明

木 $g$ を根 $r$ から遠ざかる辺のみからなる根付き木に変換する。

計算量

• $O(N)$

実装例

• convert_rooted_tree($g$, $r=0$):= 木 $g$ を根 $r$ から遠ざかる辺のみからなる根付き木に変換したものを返す

template< typename G >
G convert_rooted_tree(const G &g, int r = 0) {
  int N = (int) g.size();
  G rg(N);
  vector< int > v(N);
  v[r] = 1;
  queue< int > que;
  que.emplace(r);
  while(!que.empty()) {
    auto p = que.front();
    que.pop();
    for(auto &to : g[p]) {
      if(v[to] == 0) {
        v[to] = 1;
        que.emplace(to);
        rg[p].emplace_back(to);
      }
    }
  }
  return rg;
}