Cod sursa(job #1610284)

Utilizator xtreme77Patrick Sava xtreme77 Data 23 februarie 2016 13:35:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.1 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "biconex.in" ;
const char OUT [ ] = "biconex.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

const int MAX = 2e5 + 14 ;

vector < int > gr [ MAX ] ;

stack < pair < int , int > > st ;

int level [ MAX ] ;
int low [ MAX ] ;

bitset < MAX > viz ;

vector < int > biconex [ MAX ] ;
int cate ;

unordered_map < int , int > H ;

inline void dfs ( int nod , int lvl )
{
    viz [ nod ] = 1 ;
    level [ nod ] = lvl ;
    low [ nod ] = lvl ;
    for ( auto x : gr [ nod ] )
    {
        if ( viz [ x ] == 0 ){
            st.push ( mp ( nod , x ) ) ;
            dfs ( x , lvl + 1 ) ;
            if ( low [ x ] < low [ nod ] ){
                low [ nod ] = low [ x ] ;
            }
            if ( low [ x ] >= level [ nod ] ) {
                H.clear ( ) ;
                ++ cate ;
                while ( !st.empty() and !( st.top().first == nod and st.top().second == x ) )
                {
                    if ( H [ st.top().first ] == 0 ) {
                        biconex [ cate ].pb ( st.top().first ) ;
                        H [ st.top().first ] = 1 ;
                    }
                    if ( H [ st.top().second ] == 0 ) {
                        biconex [ cate ].pb ( st.top().second ) ;
                        H [ st.top().second ] = 1 ;
                    }
                    st.pop() ;
                }
                if ( !st.empty() and st.top().first == nod and st.top().second == x ) {
                    if ( H [ st.top().first ] == 0 ) {
                        biconex [ cate ].pb ( st.top().first ) ;
                        H [ st.top().first ] = 1 ;
                    }
                    if ( H [ st.top().second ] == 0 ) {
                        biconex [ cate ].pb ( st.top().second ) ;
                        H [ st.top().second ] = 1 ;
                    }
                    st.pop() ;
                }
            }
        }
        else if ( level [ x ] <= level [ nod ] ) {
            st.push ( mp ( nod , x ) ) ;
            low [ nod ] = min ( low [ nod ] , level [ x ] ) ;
        }
    }
}

int main ( void )
{
    int n , m ;
    cin >> n >> m ;
    FORN ( i , 1 , m )
    {
        int x , y ;
        cin >> x >> y ;
        gr [ x ].pb ( y ) ;
        gr [ y ].pb ( x ) ;
    }
    dfs ( 1 , 1 ) ;
    cout << cate << '\n' ;
    FORN ( i , 1 , cate )
    {
        for ( auto x : biconex [ i ] )
            cout << x << ' ' ;
        cout << '\n' ;
    }
    return 0;
}