Cod sursa(job #1458002)

Utilizator petru.cehanCehan Petru petru.cehan Data 5 iulie 2015 15:19:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#define minim(a, b)  ((a) < (b) ? (a) : (b))

using namespace std;

ifstream fin ("ctc.in") ;
ofstream fout ("ctc.out") ;

int N , M ;
struct nod
{
    nod * next ;
    int info ;
} ;

nod * L[100001] ; // L = lista noduri adiacente pt fiecare

void Add ( int , int ) ;
void Citire ()
{
    fin >> N >> M ;
    int a , b ;
    while ( M >= 1 )
    {
        fin >> a >> b ;
        Add ( a , b ) ;
        -- M ;
    }
}

void Add ( int a , int b )
{
    nod * p = new nod ;
    p->info = b ;
    p->next = L [a] ;
    L [a] = p ;
}

int idx [100001] , lowlink [100001] , stiva [100001] , index  , top_s  , nr_comp , node ;
vector < int > sol [100001] ;
bool in_stiva [100001] ;

void TarjanDFS ( int nd )
{

    idx [ nd ] = index ;
    lowlink [ nd ] = index ;
    ++ index ;
    stiva [ ++ top_s ] = nd ;
    in_stiva [ nd ] = 1 ;
    nod * p ;

    for ( p = L [ nd ] ; p != 0 ; p = p->next )
               {
                   if ( idx [ p->info ] == -1 )
                         TarjanDFS ( p->info ) , lowlink [ nd ] = minim(lowlink [ nd ] , lowlink [ p->info ]) ;
                   else if ( in_stiva [ p->info ] == 1 )
                         lowlink [ nd ] = minim(lowlink [ nd ] , lowlink [ p->info ]) ;
               }

    if ( lowlink [ nd ] == idx [ nd ] )// este nd radacina a unei componente conexe

             {
                 ++ nr_comp ;
                 do
                    {
                       sol [ nr_comp ] .push_back ( ( node = stiva [ top_s ] ) ) ;
                       in_stiva [ node ] = 0 ;
                       -- top_s ;
                    }

                 while ( nd != node ) ;
             }

}

void CompTareConexe ()
{
    int i ;
    for ( i = 1 ; i <= N ; ++ i )
            idx [i] = -1 ;

    for ( i = 1 ; i <= N ; ++ i )
        if ( idx [i] == -1 )
            TarjanDFS (i) ;

    fout << nr_comp << "\n" ;

    for ( i = 1 ; i <= nr_comp ; ++ i )
        {
            for ( unsigned int j = 0 ; j < sol [i].size() ; ++ j )
                  fout << sol [i][j] << " " ;
            fout << "\n" ;
        }
}

int main ()
{
    Citire () ;
    CompTareConexe () ;
    return 0 ;
}