根付き木変換
(library/graph/tree/convert_rooted_tree.hpp)

• View this file on GitHub
• Last update: 2026-01-21 14:59:16+09:00
• Include: #include "library/graph/tree/convert_rooted_tree.hpp"

根付き木変換

できること

• 無向グラフな木を、「親から子への方向」をもつ、有向グラフな木に変換する
• BFSを用いて、指定した頂点から遠ざかる方向にのみ辺を張り直している

計算量

$O(N + M)$ Nは頂点数、Mは辺の数

使い方

Graph rG = convert_rooted_tree(G, 0);

Depends on

• 辺 (library/graph/base/edge.hpp)
• グラフ (library/graph/base/graph.hpp)

Verified with

• 木 - 根付き木変換のテスト (tests/graph.tree.convert_rooted_tree.test.cpp)

Code

#pragma once
#include "library/graph/base/graph.hpp"
Graph convert_rooted_tree(const Graph &G, int r = 0) {
    int N = (int)G.size();
    Graph 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 &&edge : G[p]) {
            if (v[edge.to] == 0ll) {
                v[edge.to] = 1;
                que.emplace(edge.to);
                rg.G[p].emplace_back(edge);
            }
        }
    }
    return rg;
}

#line 2 "library/graph/base/edge.hpp"
struct Edge {
    int from, to;
    long long cost;
    int idx;
    Edge(int from, int to, long long cost = 1, int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}
};
#line 3 "library/graph/base/graph.hpp"
struct Graph {
    int N;
    vector<vector<Edge>> G;
    int es;
    Graph() = default;
    Graph(int N) : N(N), G(N), es(0) {}
    const vector<Edge> &operator[](int v) const { return G[v]; }
    int size() const { return N; }
    void add(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es++));
    }
    void add_both(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es));
        G[to].push_back(Edge(to, from, cost, es++));
    }
    void read(int M, int padding = -1, bool weighted = false,
              bool directed = false) {
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            u += padding, v += padding;
            long long cost = 1ll;
            if (weighted) cin >> cost;
            if (directed) {
                add(u, v, cost);
            } else {
                add_both(u, v, cost);
            }
        }
    }
};
#line 3 "library/graph/tree/convert_rooted_tree.hpp"
Graph convert_rooted_tree(const Graph &G, int r = 0) {
    int N = (int)G.size();
    Graph 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 &&edge : G[p]) {
            if (v[edge.to] == 0ll) {
                v[edge.to] = 1;
                que.emplace(edge.to);
                rg.G[p].emplace_back(edge);
            }
        }
    }
    return rg;
}

Back to top page