Algoogle

Algorithm for Programming Contest

関節点

基本情報


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

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

解説


コード


(articulation-point.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
using graph = vector<vector<int>>;
struct articulation {
    const int n; graph G;
    int cnt;
    vector<int> num, low, is_art;
    void dfs(int v) {
        num[v] = low[v] = ++cnt;
        for (int nv : G[v]) {
            if (num[nv] == 0) {
                dfs(nv);
                low[v] = min(low[v], low[nv]);
                if ((num[v] == 1 and num[nv] != 2) or
                    (num[v] != 1 and low[nv] >= num[v])) {
                    is_art[v] = true;
                }
            } else {
                low[v] = min(low[v], num[nv]);
            }
        }
    }
    articulation(const graph& G) : n(G.size()), G(G), cnt(0), num(n), low(n), is_art(n) {
        rep(i, n) if (num[i] == 0) dfs(i);
    }
};

問題


Comments