Cod sursa(job #852912)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 11 ianuarie 2013 21:48:39
Problema Componente biconexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 2.24 kb
#include <cstdio>
#include <cstdlib>
#include <vector>

#define nmax 10000

using namespace std ;

int stiva [ nmax ] , aaa ;
int N , M , stiva_nr , nr_componente ;
vector<int> vecini [ nmax ] , biconexe [ nmax ] ;
int t [ nmax ] , niv [ nmax ] , l [ nmax ] ;
bool valid [ nmax ] ;

void citire ()
{
    FILE *fin ;
    fin = fopen ( "biconex.in" , "rt" ) ;

    fscanf ( fin , "%d %d" , &N , &M ) ;
    for ( int i = 1 ; i <= M ; i++ )
    {
        int a , b ;
        fscanf ( fin , "%d %d" , &a , &b ) ;
        vecini [ a ].push_back ( b ) ;
        vecini [ b ].push_back ( a ) ;
    }
    l [ 1 ] = 1 ;
    t [ 1 ] = 0 ;
    niv [ 1 ] = 1 ;
    for ( int i = 1 ; i <= N ; i++ )
        valid [ i ] = 1 ;
}
void stiva_adauga ( int aaa )
{
    stiva_nr++ ;
    stiva [ stiva_nr ] = aaa ;
}
void gasit_componenta ( int nod )
{
    nr_componente++ ;
    while ( stiva [ stiva_nr ] != nod )
    {
        biconexe[ nr_componente ].push_back ( stiva [ stiva_nr ] ) ;
        stiva_nr-- ;

    }
    biconexe[ nr_componente ].push_back ( stiva [ stiva_nr ] ) ;
}

void dfs ( int nod )
{
    valid [ nod ] = 0 ;
    stiva_adauga ( nod ) ;
    for ( int i = 0 ; i < vecini [ nod ].size () ; i++ )
    {
        int y = vecini [ nod ][ i ] ;
        if ( !valid [ y ] )
        {
            if ( y < t [ nod ] )
                {
                    l [ nod ] = niv [ y ] ;

                }
            continue ;
        }
        t [ y ] = nod ;
        niv [ y ] = niv [ nod ] + 1 ;
        l [ y ] = niv [ y ] ;
        dfs ( y ) ;

        if ( l [ nod ] > l [ y ] ) l [ nod ] = l [ y ] ;
        if ( l [ y ] >= niv [ t [ y ] ] )  gasit_componenta ( t [ y ] )  ;

    }
}
int main ()
{
    citire () ;
    for ( int i = 1 ; i <= N ; i++ )
        if ( valid [ i ] )
        {
            niv [ i ] = 1 ;
            dfs ( i ) ;
        }

    FILE *fout ;
    fout = fopen ( "biconex.out" , "wt" ) ;


    fprintf ( fout , "%d\n" , nr_componente ) ;
    for ( int i = 1 ; i <= nr_componente ; i++ )
    {
        for ( int j = biconexe [ i ].size () - 1 ; j >= 0 ; j-- )
            fprintf ( fout , "%d " , biconexe[ i ][j] ) ;
        fprintf ( fout , "\n" ) ;
    }

    return 0 ;
}