test/src/graph/two_edge_connected_components/two_edge_connected_components.test.cpp

View this file on GitHub
Last update: 2024-01-30 20:12:06+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 <iostream>

#include "library/graph/two_edge_connected_components.hpp"
using suisen::TwoEdgeConnectedComponents;

auto solve1(int n, std::vector<std::pair<int, int>> edges) {
    TwoEdgeConnectedComponents tecc(n, edges);
    return std::make_pair(tecc.component_num(), tecc.groups());
}
auto solve2(int n, std::vector<std::pair<int, int>> edges) {
    TwoEdgeConnectedComponents tecc(n);
    for (auto &[u, v] : edges) {
        tecc.add_edge(u, v);
    }
    tecc.build();
    return std::make_pair(tecc.component_num(), tecc.groups());
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int, int>> edges(m);
    for (auto &[u, v] : edges) std::cin >> u >> v;

    auto ans1 = solve1(n, edges);
    auto ans2 = solve2(n, edges);

    assert(ans1 == ans2);

    const auto &[comp_num, groups] = ans1;

    std::cout << comp_num << '\n';
    for (const auto &group : groups) {
        std::cout << group.size();
        for (const int v : group) std::cout << ' ' << v;
        std::cout << '\n';
    }
    return 0;
}

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

#include <iostream>

#line 1 "library/graph/two_edge_connected_components.hpp"



#line 1 "library/graph/low_link.hpp"



#include <cassert>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>

namespace suisen {
    struct LowLink {
        LowLink() : LowLink(0) {}
        LowLink(const int n) : _n(n), _m(0), _g(n), _pre_order(n, -1), _low_link(n), _built(false), _conn_comp_num(0), _par(n, -1) {}
        LowLink(const int n, const std::vector<std::pair<int, int>> &edges) : LowLink(n) {
            for (const auto &[u, v] : edges) add_edge(u, v);
            build();
        }
        
        // Add an edge and return its ID. IDs are assigned in the order (0,1,2, ...).
        int add_edge(int u, int v) {
            _built = false;
            _edges.emplace_back(u, v);
            _g[u].emplace_back(v, _m);
            _g[v].emplace_back(u, _m);
            return _m++;
        }

        void build() {
            dfs_for_all_connected_components();
            _built = true;
        }

        int vertex_num() const { return _n; }
        int edge_num()   const { return _m; }

        const std::pair<int, int>& edge(int edge_id) const { return _edges[edge_id]; }
        const std::vector<std::pair<int, int>>& edges() const { return _edges; }
        // list of edges { u, edge_id } adjacent to the vertex v.
        const std::vector<std::pair<int, int>>& operator[](int v) const { return _g[v]; }
        
        int pre_order(int v) const {
            assert(_built);
            return _pre_order[v];
        }
        int low_link(int v) const {
            assert(_built);
            return _low_link[v];
        }

        // Returns IDs of bridges.
        const std::vector<int>& bridge_ids() const {
            assert(_built);
            return _bridges;
        }
        const std::vector<int>& articulation_points() const {
            assert(_built);
            return _articulation_points;
        }

        // O(1)
        // Assuming that there exists the edge {u,v}, return whether the edge is a bridge or not.
        bool is_bridge(int u, int v) const {
            assert(_built);
            if (_pre_order[u] > _pre_order[v]) std::swap(u, v);
            // u is an ancestor of v
            return _pre_order[u] < _low_link[v];
        }

        // O(# edges incident with u)
        // Return whether the vertex is a articulation point or not.
        bool is_articulation_point(int u) const {
            assert(_built);
            return connected_component_num_if_removed(u) > connected_component_num();
        }

        // Return the number of connected components
        int connected_component_num() const {
            assert(_built);
            return _conn_comp_num;
        }

        // O(1)
        // Assuming that there exists the edge {u,v}, return the number of connected components of the graph obtained by removing an edge {u,v}.
        // If there are multiple edges {u,v}, consider removing only one of them.
        int connected_component_num_if_removed(int u, int v) const {
            assert(_built);
            return _conn_comp_num + is_bridge(u, v);
        }

        // O(# edges incident with u)
        // Return the number of connected components of the graph obtained by removing an vertex u and edges incident with it.
        int connected_component_num_if_removed(int u) const {
            assert(_built);
            static std::vector<int8_t> seen;
            if (seen.size() < size_t(_n)) seen.resize(_n);
            bool is_root = true;
            int res = 0;
            for (const auto& [v, _] : _g[u]) {
                if (_pre_order[v] < _pre_order[u]) {
                    is_root = false;
                    continue;
                }
                if (_par[v] == u and not std::exchange(seen[v], true)) {
                    res += (_pre_order[u] <= _low_link[v]);
                }
            }
            // rollback
            for (const auto& [v, _] : _g[u]) seen[v] = false;
            return _conn_comp_num - 1 + res + (not is_root);
        }
    protected:
        int _n, _m;
        // list of edges
        std::vector<std::pair<int, int>> _edges;
        // vertex -> list of (adjacent vertex, edge id)
        std::vector<std::vector<std::pair<int, int>>> _g;
        // vertex -> pre order
        std::vector<int> _pre_order;
        std::vector<int> _low_link;
        // list of ids of bridges
        std::vector<int> _bridges;
        std::vector<int> _articulation_points;

        bool _built;

    private:
        // # connected components
        int _conn_comp_num;
        std::vector<int> _par;

        void dfs(const int u, const int prev_id, int& ord) {
            const bool is_root = prev_id < 0;
            bool is_articulation_point = false;
            int ch_cnt = 0;
            _pre_order[u] = _low_link[u] = ord++;
            for (const auto& [v, id] : _g[u]) if (id != prev_id) {
                if (_pre_order[v] < 0) {
                    _par[v] = u;
                    ++ch_cnt;
                    dfs(v, id, ord);
                    _low_link[u] = std::min(_low_link[u], _low_link[v]);
                    if (_pre_order[u] <= _low_link[v]) {
                        is_articulation_point = not is_root;
                        if (_pre_order[u] != _low_link[v]) _bridges.push_back(id);
                    }
                } else {
                    _low_link[u] = std::min(_low_link[u], _pre_order[v]);
                }
            }
            if (is_articulation_point or (is_root and ch_cnt > 1)) _articulation_points.push_back(u);
        }

        void dfs_for_all_connected_components() {
            for (int i = 0, ord = 0; i < _n; ++i) if (_pre_order[i] < 0) {
                dfs(i, -1, ord);
                ++_conn_comp_num;
            }
        }
    };
} // namespace suisen



#line 5 "library/graph/two_edge_connected_components.hpp"

namespace suisen {
    struct TwoEdgeConnectedComponents : public LowLink {
        TwoEdgeConnectedComponents()
            : TwoEdgeConnectedComponents(0) {}
        TwoEdgeConnectedComponents(const int n)
            : LowLink(n), _comp_id(_n, -1), _comp_num(0) {}
        TwoEdgeConnectedComponents(const int n, const std::vector<std::pair<int, int>> &edges)
            : LowLink(n, edges), _comp_id(_n, -1), _comp_num(0) {
            dfs_for_all_connected_components();
        }

        void build() {
            LowLink::build();
            dfs_for_all_connected_components();
        }

        int component_num() const {
            assert(_built);
            return _comp_num;
        }

        int operator[](int v) const {
            assert(_built);
            return _comp_id[v];
        }
        
        std::vector<std::vector<int>> groups() const {
            assert(_built);
            std::vector<std::vector<int>> res(component_num());
            for (int i = 0; i < _n; ++i) res[_comp_id[i]].push_back(i);
            return res;
        }

        // v -> list of (adjacent_vertex, edge_id)
        std::vector<std::vector<std::pair<int, int>>> reduced_forest() const {
            assert(_built);
            std::vector<std::vector<std::pair<int, int>>> reduced(_comp_num);
            for (int u = 0; u < _n; ++u) {
                for (const auto &[v, edge_id] : _g[u]) {
                    const int comp_u = (*this)[u], comp_v = (*this)[v];
                    if (comp_u != comp_v) reduced[comp_u].emplace_back(comp_v, edge_id);
                }
            }
            return reduced;
        }

    private:
        std::vector<int> _comp_id;
        int _comp_num;

        void dfs(int u, int p) {
            if (p >= 0 and _low_link[u] <= _pre_order[p]) {
                _comp_id[u] = _comp_id[p];
            } else {
                _comp_id[u] = _comp_num++;
            }
            for (const auto &e : _g[u]) {
                const int v = e.first;
                if (_comp_id[v] < 0) dfs(v, u);
            }
        }
        void dfs_for_all_connected_components() {
            _comp_num = 0;
            for (int i = 0; i < _n; ++i) {
                if (_comp_id[i] < 0) dfs(i, -1);
            }
        }
    };
} // namespace suisen



#line 6 "test/src/graph/two_edge_connected_components/two_edge_connected_components.test.cpp"
using suisen::TwoEdgeConnectedComponents;

auto solve1(int n, std::vector<std::pair<int, int>> edges) {
    TwoEdgeConnectedComponents tecc(n, edges);
    return std::make_pair(tecc.component_num(), tecc.groups());
}
auto solve2(int n, std::vector<std::pair<int, int>> edges) {
    TwoEdgeConnectedComponents tecc(n);
    for (auto &[u, v] : edges) {
        tecc.add_edge(u, v);
    }
    tecc.build();
    return std::make_pair(tecc.component_num(), tecc.groups());
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int, int>> edges(m);
    for (auto &[u, v] : edges) std::cin >> u >> v;

    auto ans1 = solve1(n, edges);
    auto ans2 = solve2(n, edges);

    assert(ans1 == ans2);

    const auto &[comp_num, groups] = ans1;

    std::cout << comp_num << '\n';
    for (const auto &group : groups) {
        std::cout << group.size();
        for (const int v : group) std::cout << ' ' << v;
        std::cout << '\n';
    }
    return 0;
}