Biconnected Components (二重頂点連結成分分解)
(lib/graph/biconnected_components.hpp)

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

Biconnected Components (二重頂点連結成分分解)

概要

グラフについて、二重頂点連結成分分解を行います。

使い方

• BiconnectedComponents(node_size): コンストラクタ (node_size は頂点数)
• add_edge(u, v): 頂点 $u$ から 頂点 $v$ に無向辺を追加します。
• build(): 二重頂点連結成分分解の計算を行います。
• get(): 二重頂点連結成分分解のそれぞれの連結成分を返します。

計算量

頂点数を $V$、辺の数を $E$ とすると、$\mathrm{O}(E + V)$

Depends on

• Low Link (lib/graph/lowlink.hpp)

Verified with

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

Code

#pragma once

/**
 * @brief Biconnected Components (二重頂点連結成分分解)
 * @docs docs/graph/biconnected_components.md
 * @see https://kntychance.hatenablog.jp/entry/2022/09/16/161858
 */

#include "../graph/lowlink.hpp"

struct BiconnectedComponents : LowLink{
    using super = LowLink;

    vector<vector<Edge>> edge_result;
    vector<vector<int>> result;

    BiconnectedComponents(const int node_size) : super(node_size){}

    void build(){
        super::build();
        vector<bool> visited(V, false);
        vector<Edge> edges;
        // 辺ベースで分解
        auto dfs = [&](auto &self, int cur, int prv) -> void {
            visited[cur] = true;
            bool is_multiple = false;
            for(auto &edge : G[cur]){
                if(edge.to == prv && !is_multiple){
                    is_multiple = true;
                    continue;
                }
                if(!visited[edge.to] || ord[edge.to] < ord[cur]){
                    edges.emplace_back(edge);
                }
                if(!visited[edge.to]){
                    self(self, edge.to, cur);
                    if(ord[cur] <= low[edge.to]){
                        edge_result.push_back({});
                        while(true){
                            auto edgeb = edges.back();
                            edge_result.back().push_back(edgeb);
                            edges.pop_back();
                            if(edge.id == edgeb.id) break;
                        }
                    }
                }
            }
        };
        for(int i = 0; i < V; i++){
            if(!visited[i]){
                dfs(dfs, i, -1);
            }
        }

        vector<bool> used(V), is_exist(V);
        for(auto &x : edge_result){
            vector<int> v;
            for(auto &y : x){
                if(!is_exist[y.from]) v.push_back(y.from);
                if(!is_exist[y.to]) v.push_back(y.to);
                is_exist[y.from] = true;
                is_exist[y.to] = true;
                used[y.from] = true;
                used[y.to] = true;
            }
            for(auto &y : x){
                is_exist[y.from] = false;
                is_exist[y.to] = false;
            }
            result.push_back(v);
        }
        for(int i = 0; i < V; i++){
            if(!used[i]){
                result.push_back({i});
            }
        }
    }

    vector<vector<int>> get(){
        return result;
    }
};

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

/**
 * @brief Biconnected Components (二重頂点連結成分分解)
 * @docs docs/graph/biconnected_components.md
 * @see https://kntychance.hatenablog.jp/entry/2022/09/16/161858
 */

#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;
        }
    }
};
#line 10 "lib/graph/biconnected_components.hpp"

struct BiconnectedComponents : LowLink{
    using super = LowLink;

    vector<vector<Edge>> edge_result;
    vector<vector<int>> result;

    BiconnectedComponents(const int node_size) : super(node_size){}

    void build(){
        super::build();
        vector<bool> visited(V, false);
        vector<Edge> edges;
        // 辺ベースで分解
        auto dfs = [&](auto &self, int cur, int prv) -> void {
            visited[cur] = true;
            bool is_multiple = false;
            for(auto &edge : G[cur]){
                if(edge.to == prv && !is_multiple){
                    is_multiple = true;
                    continue;
                }
                if(!visited[edge.to] || ord[edge.to] < ord[cur]){
                    edges.emplace_back(edge);
                }
                if(!visited[edge.to]){
                    self(self, edge.to, cur);
                    if(ord[cur] <= low[edge.to]){
                        edge_result.push_back({});
                        while(true){
                            auto edgeb = edges.back();
                            edge_result.back().push_back(edgeb);
                            edges.pop_back();
                            if(edge.id == edgeb.id) break;
                        }
                    }
                }
            }
        };
        for(int i = 0; i < V; i++){
            if(!visited[i]){
                dfs(dfs, i, -1);
            }
        }

        vector<bool> used(V), is_exist(V);
        for(auto &x : edge_result){
            vector<int> v;
            for(auto &y : x){
                if(!is_exist[y.from]) v.push_back(y.from);
                if(!is_exist[y.to]) v.push_back(y.to);
                is_exist[y.from] = true;
                is_exist[y.to] = true;
                used[y.from] = true;
                used[y.to] = true;
            }
            for(auto &y : x){
                is_exist[y.from] = false;
                is_exist[y.to] = false;
            }
            result.push_back(v);
        }
        for(int i = 0; i < V; i++){
            if(!used[i]){
                result.push_back({i});
            }
        }
    }

    vector<vector<int>> get(){
        return result;
    }
};

Back to top page