Cod sursa(job #854162)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 12 ianuarie 2013 21:15:21
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.83 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 vizitat [ 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 ;

}
void stiva_adauga ( muchie aaa )
{
    stiva_nr++ ;
    stiva [ stiva_nr ] = aaa ;
}
void gasit_componenta ( int nod )
{

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

void dfs ( int nod )
{
    vizitat [ nod ] = 1 ;
     for ( int i = 0 ; i < vecini [ nod ].size () ; i++ )
    {
        int y = vecini [ nod ][ i ] ;
        if ( vizitat [ y ] )
        {
            if ( y < t [ nod ] )
                {
                  if ( l [ nod ] > l [ y ] )  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 [ nod ] )  gasit_componenta ( nod )  ;

    }
}
int main ()
{
    citire () ;
    for ( int i = 1 ; i <= N ; i++ )
        if ( !vizitat [ i ] )
        {
            niv [ i ] = 1 ;
            t [ i ] = 0 ;
            dfs ( i ) ;
            if ( stiva_nr ) nr_componente++ ;
            while ( stiva_nr )
            {
                biconexe [ nr_componente ].push_back ( stiva [ stiva_nr ].x ) ;
                biconexe [ nr_componente ].push_back ( stiva [ stiva_nr ].y ) ;
                stiva_nr--;
            }

        }


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

    fprintf ( fout , "%d\n" , nr_componente ) ;


    for ( int i = 1 ; i <= nr_componente ; 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 ;
}