Cod sursa(job #853005)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 11 ianuarie 2013 23:46:08
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.68 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define nmax 100001

using namespace std ;
struct muchie
{
    int x , y ;
}stiva [ nmax ] , var ;
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 ( muchie aaa )
{
    stiva_nr++ ;
    stiva [ stiva_nr ] = aaa ;
}
void gasit_componenta ( int nod )
{

    nr_componente++ ;
    while ( stiva [ stiva_nr ].x != nod && stiva [ stiva_nr ].y !=nod )
    {
        biconexe [ nr_componente ].push_back ( stiva [ stiva_nr ].x ) ;
        biconexe [ nr_componente ].push_back ( stiva [ stiva_nr ].y ) ;
        stiva_nr-- ;
    }

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

void dfs ( int nod )
{
    valid [ nod ] = 0 ;

    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 ] ;

        var.x = nod , var.y = y ;
        stiva_adauga ( var ) ;
        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 = nr_componente ; i >= 1 ; i-- )
    {
        sort ( biconexe [ i ].begin () , biconexe [ i ].end () );
        for ( int j = 0 ; j < biconexe [ i ].size() ; j++ )
            if ( biconexe [ i ][ j ] != biconexe [ i ][ j + 1 ]  )
                fprintf ( fout , "%d " , biconexe[i][j] ) ;
        fprintf ( fout , "\n" ) ;
    }

    fclose ( fout ) ;
    return 0 ;
}