cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Hoshinonono/cp-library

:heavy_check_mark: 二重辺連結成分分解 (TECC, Two-Edge-Connected Components)
(Graph/lowlink_tecc.hpp)

概要

二重辺連結成分分解を行うライブラリ。
コンストラクタに無向グラフを渡すとlowlinkの収得, 橋の列挙を行ってくれる。
メンバ関数のtecc()を呼び出すと、二重辺連結成分分解が開始される。
多重辺がある場合にも対応

関数名など 機能 計算量
tecc_graph(std::vector<std::vector<int>>) 宣言。 コンストラクタに無向グラフを渡す。 $\text{O} (N+M)$
std::vector<std::pair<int,int>> bridge メンバ変数。橋であるような辺を $u < v$ として、pair型で列挙される。
順番は未定義		 -
std::pair<std::vector<std::vector<int>>,
std::vector<std::vector<int>>> tecc() 		二重辺連結成分分解を行う。std::pairの返り値は次の通り。
・連結成分ごとにまとめたグラフ(森)。すなわち、橋だけで構成されるグラフ。
・連結成分に属する頂点のリストのリスト。		 $\text{O} (N)$
int [p] 頂点 $p$ が属する連結成分の番号を返す。 $\text{O} (1)$

Verified with

Code

struct tecc_graph{
    int N;
    bool TECC_flag = false;
    std::vector<std::vector<int>> &g;
    std::vector<bool> used;
    std::vector<int> order, low, comp;
    std::vector<std::pair<int,int>> bridge;
    tecc_graph(std::vector<std::vector<int>> &G) 
            : N(G.size()), g(G), used(N), order(N), low(N), comp(N, -1) {
        int timer = 0;
        for(int v = 0; v < N; v++){
            if(!used[v]) dfs_lowlink(v, -1, timer);
        }
    }
    int operator[](int p) { 
        assert(TECC_flag && 0 <= p && p < N);
        return comp[p]; 
    }
    void dfs_lowlink(int v, int par, int &timer){
        used[v] = true;
        low[v] = order[v] = timer++;
        bool par_flg = false;
        for(auto &u : g[v]){
            if(!used[u]){
                dfs_lowlink(u, v, timer);
                low[v] = std::min(low[v], low[u]);
                if(order[v] < low[u]) bridge.emplace_back(std::minmax(v, u));
                else merge(u, v);
            }else if(u != par || par_flg){
                low[v] = std::min(low[v], order[u]);
            }
            if(u == par) par_flg = true;
        }
    }
    std::pair<std::vector<std::vector<int>>, std::vector<std::vector<int>>> tecc(){
        TECC_flag = true;
        std::vector<std::vector<int>> Group(N);
        for(int i = 0; i < N; i++){
            if(comp[i] < 0) Group[i].reserve(-comp[i]);
        }
        for(int i = 0; i < N; i++) Group[leader(i)].push_back(i);
        Group.erase(
            std::remove_if(Group.begin(), Group.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            Group.end());
        for(int id = 0; id < Group.size(); id++){
            for(auto &&v : Group[id]) comp[v] = id;
        }
        std::vector<std::vector<int>> result(Group.size());
        for(auto &&e : bridge){
            int u = comp[e.first], v = comp[e.second];
            result[u].push_back(v);
            result[v].push_back(u);
        }
        return std::make_pair(result, Group);
    }
    private:
    int leader(int v){
        if(comp[v] < 0)return v;
        return comp[v] = leader(comp[v]);
    }
    void merge(int u, int v){
        int x = leader(u), y = leader(v);
        if(x == y) return;
        if (-comp[x] < -comp[y]) std::swap(x, y);
        comp[x] += comp[y];
        comp[y] = x;
    }
};
#line 1 "Graph/lowlink_tecc.hpp"
struct tecc_graph{
    int N;
    bool TECC_flag = false;
    std::vector<std::vector<int>> &g;
    std::vector<bool> used;
    std::vector<int> order, low, comp;
    std::vector<std::pair<int,int>> bridge;
    tecc_graph(std::vector<std::vector<int>> &G) 
            : N(G.size()), g(G), used(N), order(N), low(N), comp(N, -1) {
        int timer = 0;
        for(int v = 0; v < N; v++){
            if(!used[v]) dfs_lowlink(v, -1, timer);
        }
    }
    int operator[](int p) { 
        assert(TECC_flag && 0 <= p && p < N);
        return comp[p]; 
    }
    void dfs_lowlink(int v, int par, int &timer){
        used[v] = true;
        low[v] = order[v] = timer++;
        bool par_flg = false;
        for(auto &u : g[v]){
            if(!used[u]){
                dfs_lowlink(u, v, timer);
                low[v] = std::min(low[v], low[u]);
                if(order[v] < low[u]) bridge.emplace_back(std::minmax(v, u));
                else merge(u, v);
            }else if(u != par || par_flg){
                low[v] = std::min(low[v], order[u]);
            }
            if(u == par) par_flg = true;
        }
    }
    std::pair<std::vector<std::vector<int>>, std::vector<std::vector<int>>> tecc(){
        TECC_flag = true;
        std::vector<std::vector<int>> Group(N);
        for(int i = 0; i < N; i++){
            if(comp[i] < 0) Group[i].reserve(-comp[i]);
        }
        for(int i = 0; i < N; i++) Group[leader(i)].push_back(i);
        Group.erase(
            std::remove_if(Group.begin(), Group.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            Group.end());
        for(int id = 0; id < Group.size(); id++){
            for(auto &&v : Group[id]) comp[v] = id;
        }
        std::vector<std::vector<int>> result(Group.size());
        for(auto &&e : bridge){
            int u = comp[e.first], v = comp[e.second];
            result[u].push_back(v);
            result[v].push_back(u);
        }
        return std::make_pair(result, Group);
    }
    private:
    int leader(int v){
        if(comp[v] < 0)return v;
        return comp[v] = leader(comp[v]);
    }
    void merge(int u, int v){
        int x = leader(u), y = leader(v);
        if(x == y) return;
        if (-comp[x] < -comp[y]) std::swap(x, y);
        comp[x] += comp[y];
        comp[y] = x;
    }
};
Back to top page