Cod sursa(job #3040851)

Utilizator Tudor06MusatTudor Tudor06 Data 30 martie 2023 15:19:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;

vector <int> edges[NMAX + 1];
int viz[NMAX + 1];
int found_time[NMAX + 1];
int min_time[NMAX + 1];

stack <int> st;

vector <int> biconexe[NMAX];
int t = 0, nrbic = 0;

void dfs( int node, int p ) {
    viz[node] = true;
    found_time[node] = min_time[node] = ++t;
    st.push( node );
    for ( auto vec : edges[node] ) {
        if ( !viz[vec] ) {
            dfs( vec, node );
            min_time[node] = min( min_time[node], min_time[vec] );
            if ( min_time[vec] >= found_time[node] ) {
                while ( st.top() != vec ) {
                    biconexe[nrbic].push_back( st.top() );
                    st.pop();
                }
                biconexe[nrbic].push_back( vec );
                st.pop();
                biconexe[nrbic].push_back( node );
                nrbic ++;
            }
        } else if ( vec != p && found_time[vec] < found_time[node] ) {
            min_time[node] = min( min_time[node], found_time[vec] );
        }
    }
}

int main() {
    ifstream fin( "biconex.in" );
    ofstream fout( "biconex.out" );
    int n, m, i, a, b;
    fin >> n >> m;
    for ( i = 0; i < m; i ++ ) {
        fin >> a >> b;
        edges[a].push_back( b );
        edges[b].push_back( a );
    }
    for ( i = 1; i <= n; i ++ ) {
        if ( !viz[i] ) {
            dfs( i, 0 );
        }
    }

    fout << nrbic << '\n';
    for ( i = 0; i < nrbic; i ++ ) {
        for ( auto it : biconexe[i] )
            fout << it << ' ';
        fout << '\n';
    }
    return 0;
}