Cod sursa(job #2354194)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 24 februarie 2019 23:44:00
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in ( "biconex.in" ) ;
ofstream out ( "biconex.out" ) ;

const int NR = 100005 ;

vector < int > v [ NR ] ;
stack < pair < int ,int > > st ;
vector < set < int > > C ;
int n , m , x , y ;
vector < int > l ( NR , -1 ) ;
int low [ NR ] ;

void make_cb ( int const x , int const y )
{
    set < int > comp ;
    int bx ,by ;
    do
    {
        bx = st.top().first ;
        by = st.top().second ;
        st.pop() ;
        comp.insert ( bx ) ;
        comp.insert ( by ) ;

    }while ( bx != x || by != y );
   C.push_back ( comp ) ;
}

void dfs ( int nod , int father , int lvl )
{
    vector < int > :: iterator it ;
    low [ nod ] = lvl ;
    l [ nod ] = lvl ;
    for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; it ++ )
    {
        if ( *it == father )    continue ;

        if ( l [ *it ] == -1 )
        {
            st.push( { nod , *it } ) ;
            dfs ( *it , nod , lvl + 1 ) ;
            low [ nod ] = min ( low [ nod ] , low [ *it ] ) ;
            if ( low [ *it ] >= l [ nod ] )
                make_cb ( nod , *it ) ;

        }
        else    low [ nod ] = min ( low [ nod ] , l [ *it ] ) ;
    }
}


int main() {

in >> n >> m ;
while ( m -- )
{
    in >> x >> y ;
    v [ x ].push_back( y ) ;
    v [ y ].push_back( x ) ;
}

dfs ( 1 , 0 , 0 ) ;

out << C.size() << '\n' ;

for ( size_t i = 0 ; i < C.size() ; ++ i , out << '\n' )
 for ( set < int > :: iterator it = C [ i ].begin() ; it != C [ i ].end() ; ++ it )  out << *it << ' ' ;

    return 0;
}