competitive-programing

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

View the Project on GitHub Astral-23/competitive-programing

:heavy_check_mark: verify/bi_connected.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components"
#include "../Utility/template.hpp"
#include "../Graph/lowlink.hpp"
#include "../Graph/bi_connected.hpp"

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

    bi_connected_components bi(g);
    cout << bi.sz << endl;
    int e_cnt = 0;
    rep(i, 0, bi.sz) e_cnt += bi.bc[i].size();
    assert(e_cnt == m);

    rep(i, 0, bi.sz) {
        vec<int> vvv;
        for (auto [u, v] : bi.bc[i]) vvv.push_back(u), vvv.push_back(v);
        sort(all(vvv));
        vvv.erase(unique(all(vvv)), vvv.end());
        sort(all(bi.vs[i]));
        if (bi.vs[i].size() == 1) {
            assert(vvv.empty());
        } else {
            assert(vvv == bi.vs[i]);
        }

        cout << bi.vs[i].size() << " ";
        for (auto v : bi.vs[i]) cout << v << " ";
        cout << '\n';
    }
}
#line 1 "verify/bi_connected.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/biconnected_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/bi_connected.hpp"
struct bi_connected_components : lowlink {
    using lowlink::aux;
    using lowlink::in;
    using lowlink::low;
    using lowlink::n;
    using lowlink::tr;

    int sz;            // 成分の個数。
    vec<vec<int>> vs;  // 頂点リスト。
    vec<vec<pair<int, int>>> bc;  // 辺リスト。vs[i] と bc[i]は同じグループ。
    vec<bool> seen;    // 補助

    bi_connected_components(const vvi &G)
        : lowlink(G), sz(0), vs(n), bc(n), seen(n, false) {
        auto dfs_make = [&](auto f, int v) -> void {
            vs[sz].push_back(v);
            seen[v] = true;
            for (int to : tr[v]) {
                if (seen[to] == false) {
                    bc[sz].emplace_back(minmax(v, to));
                    f(f, to);
                }
            }
            for (int to : aux[v]) {
                bc[sz].emplace_back(minmax(v, to));
            }
        };

        auto dfs = [&](auto f, int v, int root) -> void {
            for (int to : tr[v]) {
                f(f, to, root);
            }

            for (int to : tr[v])
                if (low[to] >= in[v]) {
                    dfs_make(dfs_make, to);
                    bc[sz].emplace_back(minmax(v, to));
                    vs[sz].push_back(v);
                    sz++;
                }

            if (v == root && tr[v].size() == 0) {
                dfs_make(dfs_make, v);
                sz++;
            }
        };

        rep(i, 0, n) if (seen[i] == false) { dfs(dfs, i, i); }
        vs.resize(sz);
        bc.resize(sz);
    }
};

struct block_cut_tree : bi_connected_components {
    using bi_connected_components::vs;
    using lowlink::aux;
    using lowlink::in;
    using lowlink::low;
    using lowlink::n;
    using lowlink::tr;

    vec<vec<int>> bct;
    vec<int> bct_rev;
    vec<vec<int>> bct_vs;
    int vsz;
    block_cut_tree(const vvi &G)
        : bi_connected_components(G),
          bct(joints.size() + vs.size()),
          bct_rev(n),
          bct_vs(joints.size() + vs.size()) {
        int id = 0;
        rep(i, 0, n) if (is_joint(i)) {
            bct_vs[id].push_back(i);
            bct_rev[i] = id;
            id++;
        }

        rep(i, 0, vs.size()) {
            for (int v : vs[i]) {
                if (is_joint(v)) {
                    bct[id].push_back(bct_rev[v]);
                    bct[bct_rev[v]].push_back(id);
                } else {
                    bct_vs[id].push_back(v);
                    bct_rev[v] = id;
                }
            }
            id++;
        }
    }

    int operator()(int v) const { return bct_rev[v]; }
};

/*
@brief 二重辺連結成分分解・BCT Tree
*/
#line 5 "verify/bi_connected.test.cpp"

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

    bi_connected_components bi(g);
    cout << bi.sz << endl;
    int e_cnt = 0;
    rep(i, 0, bi.sz) e_cnt += bi.bc[i].size();
    assert(e_cnt == m);

    rep(i, 0, bi.sz) {
        vec<int> vvv;
        for (auto [u, v] : bi.bc[i]) vvv.push_back(u), vvv.push_back(v);
        sort(all(vvv));
        vvv.erase(unique(all(vvv)), vvv.end());
        sort(all(bi.vs[i]));
        if (bi.vs[i].size() == 1) {
            assert(vvv.empty());
        } else {
            assert(vvv == bi.vs[i]);
        }

        cout << bi.vs[i].size() << " ";
        for (auto v : bi.vs[i]) cout << v << " ";
        cout << '\n';
    }
}
Back to top page