Low Link
(lib/graph/lowlink.hpp)

• View this file on GitHub
• Last update: 2024-10-31 23:51:11+09:00
• Include: #include "lib/graph/lowlink.hpp"
• Link: https://kntychance.hatenablog.jp/entry/2022/09/16/161858

Required by

• Biconnected Components (二重頂点連結成分分解) (lib/graph/biconnected_components.hpp)
• Two Edge Connected Components (二重辺連結成分分解) (lib/graph/two_edge_connected_components.hpp)

Verified with

• test/library_checker/graph/biconnected_components.test.cpp
• test/library_checker/graph/two_edge_connected_components.test.cpp

Code

#pragma once

/**
 * @brief Low Link
 * @see https://kntychance.hatenablog.jp/entry/2022/09/16/161858
 */

struct LowLink{
    struct Edge{
        int from, to, id;
    };
    vector<vector<Edge>> G;
    int V = 0, E = 0;
    vector<bool> used;
    vector<int> ord, low;
    vector<int> reachable;
    vector<pair<int, int>> bridges; // 橋
    vector<int> articulations; // 関節点
    vector<bool> is_bridge, is_articulation;

    LowLink(const int node_size) : V(node_size){
        G.resize(V);
    }

    void add_edge(int from, int to){
        G[from].push_back({from, to, E});
        G[to].push_back({to, from, E});
        E++;
    }

    void build(){
        used.assign(G.size(), 0);
        ord.assign(G.size(), 0);
        low.assign(G.size(), 0);
        reachable.assign(G.size(), -1);
        is_bridge.assign(E, false);
        is_articulation.assign(V, false);

        int k = 0;
        for(int i = 0; i < (int) G.size(); i++){
            if(!used[i]) dfs(i, -1, k);
        }
    }

    void dfs(int cur, int prv, int &k){
        used[cur] = true;
        ord[cur] = k++;
        low[cur] = ord[cur];
        bool flag_articulation = false;
        int child_count = 0; // DFS 木の子の数

        bool is_multiple = false;
        for(auto &edge : G[cur]){
            if(edge.to == prv && !is_multiple){
                is_multiple = true;
                continue;
            }
            if(!used[edge.to]){
                child_count++;
                dfs(edge.to, cur, k);
                low[cur] = min(low[cur], low[edge.to]);
                if(prv != -1 && ord[cur] <= low[edge.to]){
                    flag_articulation = true;
                }
                if(ord[cur] < low[edge.to]){
                    bridges.emplace_back(min(cur, edge.to), max(cur, edge.to));
                    is_bridge[edge.id] = true;
                }
            }else{ // 後退辺
                low[cur] = min(low[cur], ord[edge.to]);
            }
        }
        if(prv == -1 && child_count >= 2) flag_articulation = true;
        if(flag_articulation){
            articulations.push_back(cur);
            is_articulation[cur] = true;
        }
    }
};

#line 2 "lib/graph/lowlink.hpp"

/**
 * @brief Low Link
 * @see https://kntychance.hatenablog.jp/entry/2022/09/16/161858
 */

struct LowLink{
    struct Edge{
        int from, to, id;
    };
    vector<vector<Edge>> G;
    int V = 0, E = 0;
    vector<bool> used;
    vector<int> ord, low;
    vector<int> reachable;
    vector<pair<int, int>> bridges; // 橋
    vector<int> articulations; // 関節点
    vector<bool> is_bridge, is_articulation;

    LowLink(const int node_size) : V(node_size){
        G.resize(V);
    }

    void add_edge(int from, int to){
        G[from].push_back({from, to, E});
        G[to].push_back({to, from, E});
        E++;
    }

    void build(){
        used.assign(G.size(), 0);
        ord.assign(G.size(), 0);
        low.assign(G.size(), 0);
        reachable.assign(G.size(), -1);
        is_bridge.assign(E, false);
        is_articulation.assign(V, false);

        int k = 0;
        for(int i = 0; i < (int) G.size(); i++){
            if(!used[i]) dfs(i, -1, k);
        }
    }

    void dfs(int cur, int prv, int &k){
        used[cur] = true;
        ord[cur] = k++;
        low[cur] = ord[cur];
        bool flag_articulation = false;
        int child_count = 0; // DFS 木の子の数

        bool is_multiple = false;
        for(auto &edge : G[cur]){
            if(edge.to == prv && !is_multiple){
                is_multiple = true;
                continue;
            }
            if(!used[edge.to]){
                child_count++;
                dfs(edge.to, cur, k);
                low[cur] = min(low[cur], low[edge.to]);
                if(prv != -1 && ord[cur] <= low[edge.to]){
                    flag_articulation = true;
                }
                if(ord[cur] < low[edge.to]){
                    bridges.emplace_back(min(cur, edge.to), max(cur, edge.to));
                    is_bridge[edge.id] = true;
                }
            }else{ // 後退辺
                low[cur] = min(low[cur], ord[edge.to]);
            }
        }
        if(prv == -1 && child_count >= 2) flag_articulation = true;
        if(flag_articulation){
            articulations.push_back(cur);
            is_articulation[cur] = true;
        }
    }
};

Back to top page