test/library_checker/graph/two_edge_connected_components.test.cpp

View this file on GitHub
Last update: 2024-10-31 23:51:11+09:00
Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/graph/two_edge_connected_components.hpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<vector<int>> G(n);
    TwoEdgeConnectedComponents tecc(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        tecc.add_edge(a, b);
    }
    tecc.build();
    auto ans = tecc.get();
    cout << ans.size() << '\n';
    for(auto &x : ans){
        cout << x.size();
        for(auto &y : x){
            cout << ' ' << y;
        }
        cout << '\n';
    }
}

#line 1 "test/library_checker/graph/two_edge_connected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"
#include <bits/stdc++.h>
using namespace std;

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

/**
 * @brief Two Edge Connected Components (二重辺連結成分分解)
 * @docs docs/graph/two_edge_connected_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/two_edge_connected_components.hpp"

struct TwoEdgeConnectedComponents : LowLink{
    using super = LowLink;

    vector<vector<int>> result;

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

    void build(){
        super::build();
        vector<bool> visited(V, false);
        vector<int> v;
        auto dfs = [&](auto &self, int cur) -> void {
            visited[cur] = true;
            v.push_back(cur);
            for(auto &edge : G[cur]){
                if(visited[edge.to]) continue;
                if(!is_bridge[edge.id]){
                    self(self, edge.to);
                }
            }
        };
        for(int i = 0; i < V; i++){
            if(!visited[i]){
                v.clear();
                dfs(dfs, i);
                result.push_back(v);
            }
        }
    }

    vector<vector<int>> get(){
        return result;
    }
};
#line 6 "test/library_checker/graph/two_edge_connected_components.test.cpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<vector<int>> G(n);
    TwoEdgeConnectedComponents tecc(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        tecc.add_edge(a, b);
    }
    tecc.build();
    auto ans = tecc.get();
    cout << ans.size() << '\n';
    for(auto &x : ans){
        cout << x.size();
        for(auto &y : x){
            cout << ' ' << y;
        }
        cout << '\n';
    }
}