test/yosupo/two_edge_connected_components.test.cpp

View this file on GitHub
Last update: 2024-01-08 13:32:33+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 "../../graph/lowlink.hpp"
#include "../../graph/two_edge_connected_components.hpp"

#include <bits/stdc++.h>
using namespace std;

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

    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    Lowlink low(G);
    auto comp = two_edge_connected_components(G, low);
    vector<vector<int>> ans(*max_element(comp.begin(), comp.end()) + 1);
    for (int i = 0; i < N; ++i) ans[comp[i]].push_back(i);
    cout << ans.size() << "\n";
    for (auto& v : ans) {
        cout << v.size();
        for (int u : v) cout << " " << u;
        cout << "\n";
    }
}

#line 1 "test/yosupo/two_edge_connected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"

#line 2 "graph/lowlink.hpp"
#include <algorithm>
#include <utility>
#include <vector>

class Lowlink {
   public:
    std::vector<int> ord, low;
    std::vector<std::pair<int, int>> bridge;
    std::vector<int> articulation;

    Lowlink() = default;
    explicit Lowlink(const std::vector<std::vector<int>>& G)
        : ord(G.size(), -1), low(G.size()), G(G) {
        for (int i = 0; i < (int)G.size(); ++i) {
            if (ord[i] == -1) dfs(i, -1);
        }
    }

    bool is_bridge(int u, int v) const {
        if (ord[u] > ord[v]) std::swap(u, v);
        return ord[u] < low[v];
    }

   private:
    std::vector<std::vector<int>> G;
    int k = 0;

    void dfs(int v, int p) {
        ord[v] = k++;
        low[v] = ord[v];
        bool is_articulation = false, checked = false;
        int cnt = 0;
        for (int c : G[v]) {
            if (c == p && !checked) {
                checked = true;
                continue;
            }
            if (ord[c] == -1) {
                ++cnt;
                dfs(c, v);
                low[v] = std::min(low[v], low[c]);
                if (p != -1 && ord[v] <= low[c]) is_articulation = true;
                if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c));
            } else {
                low[v] = std::min(low[v], ord[c]);
            }
        }
        if (p == -1 && cnt > 1) is_articulation = true;
        if (is_articulation) articulation.push_back(v);
    }
};
#line 4 "graph/two_edge_connected_components.hpp"

#line 6 "graph/two_edge_connected_components.hpp"

std::vector<int> two_edge_connected_components(
    const std::vector<std::vector<int>>& G, const Lowlink& low) {
    int k = 0;
    std::vector<int> comp(G.size(), -1);

    auto dfs = [&](const auto& dfs, int u) -> void {
        comp[u] = k;
        for (int v : G[u]) {
            if (comp[v] == -1 && !low.is_bridge(u, v)) dfs(dfs, v);
        }
    };

    for (int v = 0; v < (int)G.size(); ++v) {
        if (comp[v] == -1) {
            dfs(dfs, v);
            ++k;
        }
    }
    return comp;
}

std::vector<std::vector<int>> contract(const std::vector<std::vector<int>>& G,
                                       const std::vector<int>& comp) {
    const int n = *std::ranges::max_element(comp) + 1;
    std::vector<std::vector<int>> G2(n);
    for (int i = 0; i < (int)G.size(); ++i) {
        for (int j : G[i]) {
            if (comp[i] != comp[j]) {
                G2[comp[i]].push_back(comp[j]);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        std::ranges::sort(G2[i]);
        G2[i].erase(std::ranges::unique(G2[i]).begin(), G2[i].end());
    }
    return G2;
}
#line 5 "test/yosupo/two_edge_connected_components.test.cpp"

#include <bits/stdc++.h>
using namespace std;

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

    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    Lowlink low(G);
    auto comp = two_edge_connected_components(G, low);
    vector<vector<int>> ans(*max_element(comp.begin(), comp.end()) + 1);
    for (int i = 0; i < N; ++i) ans[comp[i]].push_back(i);
    cout << ans.size() << "\n";
    for (auto& v : ans) {
        cout << v.size();
        for (int u : v) cout << " " << u;
        cout << "\n";
    }
}