Cod sursa(job #2679180)

Utilizator mihnea.anghelMihnea Anghel mihnea.anghel Data 29 noiembrie 2020 20:21:43
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#define f in
#define g out

using namespace std;
ifstream in ( "biconex.in" );
ofstream out( "biconex.out" );
int n, m, i, x, y, cbc;
int low[100100], viz[100100], niv[100100];
vector<int> L[100100], v, comp[100100];

void dfs ( int nod, int tata, int nivel ){
    viz[nod] = 1;
    low[nod] = niv[nod] = nivel;
    v.push_back(nod);
    for ( auto vecin : L[nod] ){
        if ( vecin == tata )
            continue;
        if ( viz[vecin] ){
            low[nod] = min ( low[nod], low[vecin] );
            continue;
        }
        dfs(vecin, nod, nivel+1);
        low[nod] = min ( low[nod], low[vecin] );
        if ( low[vecin] >= niv[nod] ){
            cbc++;
            x = 0;
            while ( x != vecin ) {
                x = v.back();
                v.pop_back();
                comp[cbc].push_back(x);
            }
            comp[cbc].push_back(nod);
        }
    }
}

int main() {
    f>>n>>m;
    for ( i=1; i <= m; i++ ){
        f>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    dfs ( 1, 0, 1 );
    g<<cbc<<"\n";
    for ( i=1; i <= cbc; i++, g<<"\n" )
        for ( auto x : comp[i] )
            g<<x<<" ";
    return 0;
}