Cod sursa(job #1457824)

Utilizator petru.cehanCehan Petru petru.cehan Data 4 iulie 2015 15:43:45
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 3.18 kb
// Algortimul lui Tarjan   COMPL : O ( N+M )  // varianta lui Kosaraju imbunatatit
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

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

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

struct fractie
{
    int numarator ;
    int numitor ;
} ;

fractie F [100001] ; // pentru a tine numaratorii / numitorii nodurilor ;
bool viz [100001] , vizt [100001] ; // vizitori pentru GrafNormal si respectiv GrafTranspus

int sortat [200002] ; // pentru a evita sortarea
int nr = 0 ;

void DFS ( int nd ) // calculez numaratorii si numitorii
{
    viz [nd] = 1 ;
    F [ nd ].numarator = ++ nr ;
    nod * p ;
    for ( p = L [nd] ; p != 0 ; p = p->next )
           if ( viz [ p->info ] == 0 )
                   DFS ( p->info ) ;

    F [ nd ].numitor =  ++ nr ;
    sortat [ F [ nd ].numitor ] = nd ;

}

void DFSS ( int nd ) // completez unde a ramas 0 ..adica unde nu s-a putut ajunge din nodul nd
{
    DFS (nd) ;
    for ( int i = 1 ; i <= N ; ++ i )
         if ( viz [i] == 0 )
              F [i].numarator = ++ nr , F [i].numitor = ++ nr , sortat [ F [i].numitor ] = i ;
}

/*bool cmp ( fractie i , fractie j )
{
    return ( i.numitor > j.numitor );
}*/

int nr_comp ;
vector <int> sol [100001] ;

void DFSTRANSPUS ( int nd ) // este DFS TARJAN
{
    sol [ nr_comp ] .push_back (nd) ;
    vizt [nd] = 1 ;
    nod * p ;

    for ( p = LT [nd] ; p != 0 ; p = p->next )
            if (vizt [p->info] == 0 )
                    DFSTRANSPUS (p->info) ;
}

void CompTareConexe ()
{
    int i ;
    for ( i = 1 ; i <= N ; ++ i )
        if ( viz[i] == 0 )
            DFSS (i) ;

    // merge si in O(n) .. deoarece nr = 2*N .. folosim memorie suplimentara un vector "sortat" ;
    // sort ( F + 1  , F + N + 1 , cmp ) ;
    // secv sortata descrescator dupa numitor ne spune de unde sa incepem parcurgerea de fiecare data pt a gasit comp conexe ;

       for ( i = nr ; i >= 1 ; -- i )
        {
            if ( sortat [i] != 0 && vizt [ sortat [i] ] == 0 ) // nu face parte inca din nicio comp conexa
                   ++ nr_comp , DFSTRANSPUS ( sortat [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 () ;
    GrafTranspus () ;
    CompTareConexe () ;
}