LowLink関連 (関節点, 橋)
(Graph/lowlink.hpp)

• View this file on GitHub
• Last update: 2024-01-08 00:56:38+09:00
• Include: #include "Graph/lowlink.hpp"

概要

lowlinkの収得を行うライブラリ。
コンストラクタに無向グラフを渡すと関節点、橋の列挙を行ってくれる。
計算量は、頂点数 $N$ 、辺数 $M$ として記述。
多重辺があるグラフは現段階では非対応。verifyできる問題ないのかな…

関数名など	機能	計算量
lowlink_graph(std::vector<std::vector<int>>)	宣言。 コンストラクタに無向グラフを渡す。	$\text{O} (N+M)$
std::vector<int> art_point	メンバ変数。関節点が列挙される。 順番は未定義。	-
std::vector<std::pair<int,int>> bridge	メンバ変数。橋であるような辺を $u < v$ として、pair型で列挙される。 順番は未定義	-

Verified with

• Test/Aizu Online Judge/GRL/GRL_3_A.test.cpp
• Test/Aizu Online Judge/GRL/GRL_3_B.test.cpp

Code

struct lowlink_graph{
    int N;
    std::vector<std::vector<int>>& g;
    std::vector<bool> used;
    std::vector<int> order, low, art_point;
    std::vector<std::pair<int,int>> bridge;
    lowlink_graph(std::vector<std::vector<int>> &G) 
            : N(G.size()), g(G), used(N), order(N), low(N) {
        int timer = 0;
        for(int v = 0; v < N; v++){
            if(!used[v]) dfs_lowlink(v, -1, timer);
        }
    }
    void dfs_lowlink(int v, int par, int &timer){
        used[v] = true;
        low[v] = order[v] = timer++;
        bool is_art_point = false;
        int cnt = 0;
        for(auto &u : g[v]){
            if(!used[u]){
                cnt++;
                dfs_lowlink(u, v, timer);
                low[v] = std::min(low[v], low[u]);
                is_art_point |= ~par && low[u] >= order[v];
                if(order[v] < low[u]) bridge.emplace_back(std::minmax(v, u));
            }else if(u != par){
                low[v] = std::min(low[v], order[u]);
            }
        }
        is_art_point |= par == -1 && cnt > 1;
        if(is_art_point) art_point.push_back(v);
    }
};

#line 1 "Graph/lowlink.hpp"
struct lowlink_graph{
    int N;
    std::vector<std::vector<int>>& g;
    std::vector<bool> used;
    std::vector<int> order, low, art_point;
    std::vector<std::pair<int,int>> bridge;
    lowlink_graph(std::vector<std::vector<int>> &G) 
            : N(G.size()), g(G), used(N), order(N), low(N) {
        int timer = 0;
        for(int v = 0; v < N; v++){
            if(!used[v]) dfs_lowlink(v, -1, timer);
        }
    }
    void dfs_lowlink(int v, int par, int &timer){
        used[v] = true;
        low[v] = order[v] = timer++;
        bool is_art_point = false;
        int cnt = 0;
        for(auto &u : g[v]){
            if(!used[u]){
                cnt++;
                dfs_lowlink(u, v, timer);
                low[v] = std::min(low[v], low[u]);
                is_art_point |= ~par && low[u] >= order[v];
                if(order[v] < low[u]) bridge.emplace_back(std::minmax(v, u));
            }else if(u != par){
                low[v] = std::min(low[v], order[u]);
            }
        }
        is_art_point |= par == -1 && cnt > 1;
        if(is_art_point) art_point.push_back(v);
    }
};

Back to top page