Graph/tests/bridge_biconnected.test.cpp

• View this file on GitHub
• Last update: 2022-08-09 14:38:08+08:00
• Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

• Graph/DfsTree/BridgeArticulation.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"

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

#include "../DfsTree/BridgeArticulation.h"

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
#define SZ(x) ((int)(x).size())

void dfs(int u,
        const vector<vector<int>>& g,
        const set<pair<int,int>>& bridges,
        vector<int>& comp,
        vector<bool>& visited) {
    visited[u] = true;
    comp.push_back(u);

    for (int v : g[u]) {
        if (visited[v]) continue;
        if (bridges.count({v, u}) || bridges.count({u, v})) continue;

        dfs(v, g, bridges, comp, visited);
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

    // read edges
    vector<vector<int>> g(n);
    REP(eid,m) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    UndirectedDfs tree(g);
    set<pair<int,int>> bridges(tree.bridges.begin(), tree.bridges.end());

    vector<bool> visited(n, false);
    vector<vector<int>> components;
    REP(i,n) {
        if (!visited[i]) {
            vector<int> comp;
            dfs(i, g, bridges, comp, visited);
            components.push_back(comp);
        }
    }
    cout << SZ(components) << endl;
    for (auto&& comp : components) {
        cout << SZ(comp);
        for (int x : comp) cout << ' ' << x;
        cout << endl;
    }
    return 0;
}

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

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

#line 1 "Graph/DfsTree/BridgeArticulation.h"
// UndirectedDFS, for finding bridges & articulation points {{{
// Assume already have undirected graph vector< vector<int> > G with V vertices
// Vertex index from 0
// Usage:
// UndirectedDfs tree;
// Then you can use tree.bridges and tree.articulation_points
//
// Tested:
// - https://judge.yosupo.jp/problem/two_edge_connected_components
struct UndirectedDfs {
    vector<vector<int>> g;
    int n;
    vector<int> low, num, parent;
    vector<bool> is_articulation;
    int counter, root, children;

    vector< pair<int,int> > bridges;
    vector<int> articulation_points;
    map<pair<int,int>, int> cnt_edges;

    UndirectedDfs(const vector<vector<int>>& _g) : g(_g), n(g.size()),
            low(n, 0), num(n, -1), parent(n, 0), is_articulation(n, false),
            counter(0), children(0) {
        for (int u = 0; u < n; u++) {
            for (int v : g[u]) {
                cnt_edges[{u, v}] += 1;
            }
        }
        for(int i = 0; i < n; ++i) if (num[i] == -1) {
            root = i; children = 0;
            dfs(i);
            is_articulation[root] = (children > 1);
        }
        for(int i = 0; i < n; ++i)
            if (is_articulation[i]) articulation_points.push_back(i);
    }
private:
    void dfs(int u) {
        low[u] = num[u] = counter++;
        for (int v : g[u]) {
            if (num[v] == -1) {
                parent[v] = u;
                if (u == root) children++;
                dfs(v);
                if (low[v] >= num[u])
                    is_articulation[u] = true;
                if (low[v] > num[u]) {
                    if (cnt_edges[{u, v}] == 1) {
                        bridges.push_back(make_pair(u, v));
                    }
                }
                low[u] = min(low[u], low[v]);
            } else if (v != parent[u])
                low[u] = min(low[u], num[v]);
        }
    }
};
// }}}
#line 7 "Graph/tests/bridge_biconnected.test.cpp"

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
#define SZ(x) ((int)(x).size())

void dfs(int u,
        const vector<vector<int>>& g,
        const set<pair<int,int>>& bridges,
        vector<int>& comp,
        vector<bool>& visited) {
    visited[u] = true;
    comp.push_back(u);

    for (int v : g[u]) {
        if (visited[v]) continue;
        if (bridges.count({v, u}) || bridges.count({u, v})) continue;

        dfs(v, g, bridges, comp, visited);
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

    // read edges
    vector<vector<int>> g(n);
    REP(eid,m) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    UndirectedDfs tree(g);
    set<pair<int,int>> bridges(tree.bridges.begin(), tree.bridges.end());

    vector<bool> visited(n, false);
    vector<vector<int>> components;
    REP(i,n) {
        if (!visited[i]) {
            vector<int> comp;
            dfs(i, g, bridges, comp, visited);
            components.push_back(comp);
        }
    }
    cout << SZ(components) << endl;
    for (auto&& comp : components) {
        cout << SZ(comp);
        for (int x : comp) cout << ' ' << x;
        cout << endl;
    }
    return 0;
}

Back to top page