verify/two_edge_connected.test.cpp

View this file on GitHub
Last update: 2025-01-11 19:51:13+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 "../Utility/template.hpp"
#include "../Graph/lowlink.hpp"
#include "../Graph/two_edge_connected.hpp"

int main() {
    int n, m;
    cin >> n >> m;
    vec<vec<int>> g(n);
    rep(i, 0, m) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    two_edge_connected_components two(g);
    vec<vec<int>> vs(two.sz);
    rep(i, 0, n) vs[two(i)].push_back(i);

    cout << two.sz << '\n';

    rep(i, 0, two.sz) {
        cout << vs[i].size() << " ";
        for (int v : vs[i]) cout << v << " ";
        cout << '\n';
    }
}

#line 1 "verify/two_edge_connected.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Graph/lowlink.hpp"
struct lowlink {
    using vi = vec<int>;
    using vvi = vec<vi>;
    using pii = pair<int, int>;

    int n;
    vvi tr;  // dfs木に使われる辺のみ 上から下
    vvi aux;  // dfs木に使われない辺のみ  下から上 自己辺もココ
    vi low, in, par;
    vec<pii> bridges;
    vec<int> joints;
    vec<bool> inner_is_joint;
    vec<int> self_edge_cnt;

    lowlink(const vvi &g)
        : n(g.size()),
          tr(n),
          aux(n),
          low(n, 1001001001),
          in(n, -1),
          par(n, -1),
          inner_is_joint(n, false),
          self_edge_cnt(n, 0) {
        int t = 0;
        int r = 0;
        auto dfs = [&](auto f, int v, int p) -> void {
            par[v] = p;
            in[v] = low[v] = t++;
            bool duplication = false;
            for (int to : g[v]) {
                if (in[to] == -1) {
                    tr[v].push_back(to);
                    f(f, to, v);
                } else {
                    if (to != p) {
                        if (in[to] < in[v])
                            aux[v].push_back(to);
                        else if (to == v) {
                            if ((++self_edge_cnt[v]) & 1) aux[v].push_back(to);
                        }
                        chmin(low[v], in[to]);
                    } else if (duplication == false)
                        duplication = true;
                    else {
                        aux[v].push_back(to);
                        chmin(low[v], in[to]);
                    }
                }
            }

            for (int to : tr[v]) {
                chmin(low[v], low[to]);
            }
            // 部分木について、low/inが求まった
            bool isjoint = false;
            for (int to : tr[v]) {
                if (low[to] > in[v]) bridges.emplace_back(v, to);
                if (low[to] >= in[v]) isjoint = true;
            }

            if (v != r && isjoint)
                joints.push_back(v), inner_is_joint[v] = true;
            else if (v == r) {
                if (tr[v].size() > 1)
                    joints.push_back(v), inner_is_joint[v] = true;
            }
        };

        rep(i, 0, n) if (in[i] == -1) {
            r = i;
            dfs(dfs, i, -1);
        }
    }

    bool is_bridge(int u, int v) {
        if (in[u] > in[v]) swap(u, v);
        if (par[v] != u) return false;
        if (low[v] > in[u])
            return true;
        else
            return false;
    }

    bool is_joint(int v) { return inner_is_joint[v]; }
};

/*
@brief lowlink
@docs doc/lowlink.md
*/
#line 1 "Graph/two_edge_connected.hpp"
struct two_edge_connected_components : lowlink {
    using lowlink::aux;
    using lowlink::in;
    using lowlink::low;
    using lowlink::n;
    using lowlink::tr;
    int sz;  // 成分の個数
    vi rev;  // 頂点iが属する成分の番号
    vvi g;   // 縮約グラフ
    two_edge_connected_components(const vvi &G)
        : lowlink(G), sz(0), rev(n, -1), g(n) {
        auto dfs = [&](auto f, int v, int this_id) -> void {
            rev[v] = this_id;
            for (int to : G[v])
                if (rev[to] == -1) {
                    if (is_bridge(v, to)) {
                        sz++;
                        g[this_id].push_back(sz - 1);
                        g[sz - 1].push_back(this_id);
                        f(f, to, sz - 1);
                    } else {
                        f(f, to, this_id);
                    }
                }
        };

        rep(i, 0, n) if (rev[i] == -1) {
            sz++;
            dfs(dfs, i, sz - 1);
        }
        g.resize(sz);
    }

    int operator()(int v) const { return rev[v]; }
};
/*
@brief 二重辺連結成分分解
*/
#line 5 "verify/two_edge_connected.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    vec<vec<int>> g(n);
    rep(i, 0, m) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    two_edge_connected_components two(g);
    vec<vec<int>> vs(two.sz);
    rep(i, 0, n) vs[two(i)].push_back(i);

    cout << two.sz << '\n';

    rep(i, 0, two.sz) {
        cout << vs[i].size() << " ";
        for (int v : vs[i]) cout << v << " ";
        cout << '\n';
    }
}