橋木(Bridge Tree)
(graph/bridge_tree.cpp)

• View this file on GitHub
• Last update: 2026-03-12 00:49:33+09:00

説明

無向グラフの二辺連結成分を縮約して、橋だけを辺に持つ森を作る。 連結グラフなら木、非連結グラフなら森になる。

できること

• BridgeTree g(n) 頂点数 n の graph builder を作る
• void add_edge(int u, int v) 無向辺を追加する。自己ループは内部で無視される
• int build() bridge tree を構築し、成分数を返す

使い方

build() 後は tree、nodes、edges、id を参照する。

• tree[k] bridge tree 上で成分 k に隣接する成分番号列
• nodes[k] 成分 k に含まれる元グラフ頂点集合
• edges bridge tree の辺集合。各要素は成分番号の組
• id[v] 元頂点 v が属する成分番号

tecc に内部の TwoEdgeConnectedComponents を保持しているので、必要なら ord や low も参照できる。

Depends on

• 二辺連結成分分解(Two-Edge-Connected Components) (graph/twoedgeconnectedcomponents.cpp)

Verified with

• test/aoj0377.test.cpp
• test/aoj0415.test.cpp

Code

using namespace std;

#include "twoedgeconnectedcomponents.cpp"

struct BridgeTree {
    int n, component_count;
    TwoEdgeConnectedComponents tecc;
    vector<vector<int>> tree, nodes;
    vector<pair<int, int>> edges;
    vector<int> id;

    explicit BridgeTree(int n) : n(n), component_count(0), tecc(n), id(n, -1) {}

    void add_edge(int u, int v) {
        tecc.add_edge(u, v);
    }

    int build() {
        component_count = tecc.build();
        id = tecc.bridge;
        nodes = tecc.out;
        tree.assign(component_count, {});
        edges.clear();
        for (int i = 0; i < n; ++i) {
            for (auto &&j : tecc.G[i]) {
                if (i < j && tecc.is_bridge(i, j)) {
                    int u = id[i], v = id[j];
                    tree[u].push_back(v);
                    tree[v].push_back(u);
                    edges.emplace_back(u, v);
                }
            }
        }
        return component_count;
    }
};

/**
 * @brief 橋木(Bridge Tree)
 */

#line 1 "graph/bridge_tree.cpp"
using namespace std;

#line 1 "graph/twoedgeconnectedcomponents.cpp"
class TwoEdgeConnectedComponents {
    void dfs(int i, int &pos){
        ord[i] = low[i] = pos++;
        int mul = 0;
        for (auto &&j : G[i]) {
            if(j == par[i] && !mul){
                mul = 1;
                continue;
            }
            if(~ord[j]){
                low[i] = min(low[i], ord[j]);
                continue;
            }
            par[j] = i;
            dfs(j, pos);
            size[i] += size[j];
            low[i] = min(low[i], low[j]);
        }
    }

    void dfs2(int i){
        out[bridge[i]].emplace_back(i);
        for (auto &&j : G[i]) {
            if(~bridge[j] || is_bridge(i, j)) continue;
            bridge[j] = bridge[i];
            dfs2(j);
        }
    }
public:
    vector<int> ord, low, par, bridge, size;
    vector<vector<int>> G, out;
    explicit TwoEdgeConnectedComponents(int n): ord(n, -1), low(n), par(n, -1), bridge(n, -1), size(n, 1), G(n){}

    inline bool is_bridge(int i, int j){
        if(ord[i] > ord[j]) swap(i, j);
        return ord[i] < low[j];
    }

    void add_edge(int u, int v){
        if(u != v){
            G[u].emplace_back(v);
            G[v].emplace_back(u);
        }
    }

    int build(){
        int n = G.size(), pos = 0;
        for (int i = 0; i < n; ++i) {
            if(ord[i] < 0) dfs(i, pos);
        }
        int k = 0;
        for (int i = 0; i < n; ++i) {
            if(!~bridge[i]){
                bridge[i] = k++;
                out.emplace_back();
                dfs2(i);
            }
        }
        return k;
    }
};

/**
 * @brief 二辺連結成分分解(Two-Edge-Connected Components)
 */
#line 4 "graph/bridge_tree.cpp"

struct BridgeTree {
    int n, component_count;
    TwoEdgeConnectedComponents tecc;
    vector<vector<int>> tree, nodes;
    vector<pair<int, int>> edges;
    vector<int> id;

    explicit BridgeTree(int n) : n(n), component_count(0), tecc(n), id(n, -1) {}

    void add_edge(int u, int v) {
        tecc.add_edge(u, v);
    }

    int build() {
        component_count = tecc.build();
        id = tecc.bridge;
        nodes = tecc.out;
        tree.assign(component_count, {});
        edges.clear();
        for (int i = 0; i < n; ++i) {
            for (auto &&j : tecc.G[i]) {
                if (i < j && tecc.is_bridge(i, j)) {
                    int u = id[i], v = id[j];
                    tree[u].push_back(v);
                    tree[v].push_back(u);
                    edges.emplace_back(u, v);
                }
            }
        }
        return component_count;
    }
};

/**
 * @brief 橋木(Bridge Tree)
 */

Back to top page