Algoogle

Algorithm for Programming Contest

基本情報


計算量
用途 関節点を求める

V := 頂点数 E := 辺の数

解説


コード


(bridge.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using graph = vector<vector<int>>;
struct bridge {
    const int n; graph G;
    int cnt;
    vector<int> num, low, in;
    stack<int> stk;
    vector<pair<int,int> > brid;
    vector<vector<int> > comp;
    void dfs(int v, int p) {
        num[v] = low[v] = ++cnt;
        stk.push(v), in[v] = true;
        for (const int nv : G[v]) {
            if (num[nv] == 0) {
                dfs(nv, v);
                low[v] = min(low[v], low[nv]);
            } else if (nv != p and in[nv]) {
                low[v] = min(low[v], num[nv]);
            }
        }
        if (low[v] == num[v]) {
            if (p != n) brid.eb(min(v, p), max(v, p));
            comp.eb();
            int w; do {
                w = stk.top();
                stk.pop(), in[w] = false;
                comp.back().pb(w);
            } while (w != v);
        }
    }
    bridge(const graph& G) : n(G.size()), G(G), cnt(0), num(n), low(n), in(n) {
        rep(i, n) if (num[i] == 0) dfs(i, n);
    }
};

問題


Comments