Cod sursa(job #2367119)

Utilizator LucaSeriSeritan Luca LucaSeri Data 5 martie 2019 08:43:49
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

vector< int > gr[MAXN];
stack< pair< int, int > > edges;
vector< int > sol[MAXN];
int cntbico = 0;

int level[MAXN];
int minim[MAXN];

void dfs(int node, int d) {
    level[node] = minim[node] = d;

    for(auto &x : gr[node]) {
        if(!level[x]) {
            edges.push({node, x});
            dfs(x, d + 1);
            if(minim[x] >= level[node]) {
                ++cntbico;
                int a, b;
                do {
                    tie(a, b) = edges.top();
                    sol[cntbico].emplace_back(a);
                    sol[cntbico].emplace_back(b);
                    edges.pop();
                } while(a != node || b != x);

                sort(sol[cntbico].begin(), sol[cntbico].end());
                sol[cntbico].erase(unique(sol[cntbico].begin(), sol[cntbico].end()), sol[cntbico].end());
            }
        minim[node] = min(minim[node], minim[x]);
        } else minim[node] = min(minim[node], level[x]);
    }
}
int main () {
    #ifdef HOME
        freopen("input", "r", stdin);
        #define f cin
        #define g cout
    #else
        ifstream f("biconex.in");
        ofstream g("biconex.out");
    #endif // HOME

    int n, m;
    f >> n >> m;

    for(int i = 0; i < m; ++i) {
        int a, b;
        f >> a >> b;

        gr[a].emplace_back(b);
        gr[b].emplace_back(a);
    }

    dfs(1, 1);

    g << cntbico << '\n';
    for(int i = 1; i <= cntbico; ++i) {
        for(auto &x : sol[i]) g << x << ' ';

        g << '\n';
    }
    return 0;
}