Cod sursa(job #2412863)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 22 aprilie 2019 16:54:50
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int NR = 50000 ;
ifstream in ("biconex.in") ;
ofstream out ("biconex.out") ;
vector < int > v [ NR ] ;
vector < pair < int , int > > st ;
int n , m , lvl [  100005 ] , lowest [  100005 ] ;
vector < vector < int > > ans ;
void make_cb ( int x , int y )  {
    vector < int > c;
    int cx , cy ;
    do  {
        cx = st.back().first ;
        cy = st.back().second ;
        st.pop_back() ;
        c.push_back( cx ) , c.push_back( cy ) ;
    }while ( !( cx == x && cy == y ) ) ;
    ans.push_back( c ) ;
}
void dfs ( int nod , int father )   {
    vector < int > :: iterator it ;
    lowest [ nod ] = lvl [ nod ] ;
    for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )  {
        if ( *it == father )    continue ;
        if ( !lvl [ *it ] ) {
            lvl [ *it ] = lvl [ nod ] + 1 ;
            st.push_back( mp ( nod , *it ) ) ;
            dfs( *it , nod ) ;
            lowest [ nod ] = min ( lowest [ nod ] , lowest [ *it ] ) ;
            if ( lowest [ *it ] >= lvl [ nod ] )    make_cb ( nod , *it ) ;
        }   else    {
            lowest [ nod ] = min ( lowest [ nod ] , lvl [ *it ] ) ;
        }
    }

}
int main()  {
   int x , y ;
   in >> n >> m ;
   lvl [ 1 ] = 1 ;
   while ( m -- )   {
    in >> x >> y ;
    v [ x ].push_back ( y ) ;
    v [ y ].push_back ( x ) ;
   }
   dfs( 1 , 0 ) ;
    for ( size_t i = 0 ; i < ans.size() ; ++ i , out << '\n' )   {
        sort( ans [ i ].begin() , ans[ i ].end() ) ;
        ans [ i ].erase( unique( ans [ i ].begin() , ans [ i ].end()) , ans [ i ].end() ) ;
        for ( size_t j = 0 ; j < ans [ i ].size() ; ++ j ) out << ans[ i ][ j ] << ' ' ;
    }
}