Cod sursa(job #2049524)

Utilizator retrogradLucian Bicsi retrograd Data 27 octombrie 2017 12:25:42
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.91 kb
#include <bits/stdc++.h>

using namespace std;

/**
 * Author: Simon Lindholm (adapted by Lucian Bicsi)
 * Date: 2017-04-17
 * License: CC0
 * Description: Finds all biconnected components in an undirected graph, and
 *  runs a callback for the edges in each. 
 *  Callback should operate on vector<pair<int, int>>::iterators.
 *  In a biconnected component there
 *  are at least two distinct paths between any two nodes. Note that a node can
 *  be in several components. An edge which is not in a component is a bridge,
 *  i.e., not part of any cycle.
 *
 *  To get the articulation points, look for vertices that are in more than 1 BCC.
 * Time: O(E + V)
 * Status: tested during MIPT ICPC Workshop 2017
 */

struct BCC {
    int n, timer = 0;
    vector<pair<int, int>> edges;
    vector<vector<int>> G;
    vector<int> depth, stk;

    BCC(int n) : n(n), G(n), depth(n, -1) {}

    int AddEdge(int a, int b) {
        int ret = edges.size();
        edges.emplace_back(a, b);
        G[a].push_back(ret); 
        G[b].push_back(ret);
        return ret;
    }

    template<typename Callback>
    void Solve(Callback cb) {
        for (int i = 0; i < n; ++i)
            if (depth[i] == -1)
                dfs(i, -1, 0, cb); 
    }
    
    template<typename Callback>
    int dfs(int node, int pei, int d, Callback cb) {
        depth[node] = d; int ret = d;

        for (auto ei : G[node]) if (ei != pei) {
            int vec = (edges[ei].first ^ edges[ei].second ^ node);
            if (depth[vec] != -1) {
                ret = min(ret, depth[vec]);
                if (depth[vec] < d)
                    stk.push_back(ei);
            } else {
                int sz = stk.size();
                int low = dfs(vec, ei, d + 1, cb);
                ret = min(ret, low);
                if (low == d) {
                    stk.push_back(ei);
                    cb(vector<int>(stk.begin() + sz, stk.end()));
                    stk.resize(sz);
                } else if (low < d) 
                    stk.push_back(ei);
                else {
                    cb({ei});
                }
                // else ei is a bridge
            }
        }

        return ret;
    }    
};

int main() {
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int n, m; cin >> n >> m;
    vector<vector<int>> bccs;

    BCC bcc(n);
    while (m--) {
        int a, b; cin >> a >> b;
        bcc.AddEdge(a - 1, b - 1);
    }
    bcc.Solve([&](vector<int> es) {
        vector<int> verts;
        for (auto i : es) {
            verts.push_back(bcc.edges[i].first);
            verts.push_back(bcc.edges[i].second);
        }
        sort(verts.begin(), verts.end());
        verts.erase(unique(verts.begin(), verts.end()), verts.end());

        bccs.emplace_back(move(verts));
    });

    cout << bccs.size() << '\n';
    for (auto x : bccs) {
        for (auto y : x) 
            cout << y + 1 << " ";
        cout << endl;
    }

    return 0;
}