Cod sursa(job #1457736)

Utilizator petru.cehanCehan Petru petru.cehan Data 4 iulie 2015 13:09:25
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 kb
#include <iostream>
#include <fstream>

using namespace std;

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

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

nod * L[100001] , * LT [100001] ; // L = lista noduri adiacente pt fiecare , LT = lista transpusa
// L [i] = j    =>    LT [j] = i ;

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

void GrafTranspus ()
{
    nod * p , * q ;
    for ( int i = 1 ; i <= N ; ++ i )
        for ( p = L[i] ; p != 0 ; p = p->next )
          {
              q = new nod ;
              q->info = i ;
              q->next = LT [ p->info ] ;
              LT [ p->info ] = q ;
          }
}

int viz [100001] , vizt [100001] ; // viz = folosit pentru DFS pe graful normal
// vizt = folosit pentru DFS pe graful transpus , pentru a verifica daca nodurile au fost incluse sau nu intr-o componenta conexa

int timp [100001] ; // se pun nodurile in ordine inversa terminarii vizitarii vecinilor
// de fapt este o stiva .. se vor prelua elementele in ordinea inversa introducerii lor
int nr_t ;

void DFS ( int nd )
{
   viz [nd] = 1 ;
   nod * p ;
   for ( p = L [nd] ; p != 0 ; p = p->next )
          if ( viz [p->info] == 0 )
                 DFS ( p->info ) ;

   timp [ ++ nr_t ] = nd ;

}

int sol [100001] , nr_s ;

void DFSTRANSPUS ( int nd )
{
    vizt [nd] = 1 ;
    nod * p ;
    sol [ ++ nr_s ] = nd ;
    for ( p = LT [nd] ; p != 0 ; p = p->next )
            if ( vizt [p->info] == 0 )
                  DFSTRANSPUS ( p->info ) ;

}

int nr_comp ;

void CompTareConexe ()
{
    int i ;
    for ( i = 1 ; i <= N ; ++ i )
        if ( viz[i] == 0 )
            DFS (i) ;
    for ( i = nr_t ; i >= 1 ; -- i )
         if ( vizt [ timp[i] ] == 0 )  // nu face parte inca din nicio comp conexa
                DFSTRANSPUS ( timp [i] ) , sol [ ++ nr_s ] = -1 , ++ nr_comp ;

    fout << nr_comp << "\n" ;
    for ( i = 1 ; i <= nr_s ; ++ i )
         if ( sol [i] != -1 )
              fout << sol [i] << " " ;
         else
              fout << "\n" ;
}

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