Pagini recente » Cod sursa (job #2116921) | Cod sursa (job #3163320) | Cod sursa (job #1313494) | Cod sursa (job #2537351) | Cod sursa (job #1457826)
// 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
vector <int > sortat ;
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.push_back ( 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.push_back (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 ;
vector <int> :: const_reverse_iterator it ;
for ( it = sortat.rbegin() ; it != sortat.rend() ; ++ it )
{
if ( vizt [ *it ] == 0 ) // nu face parte inca din nicio comp conexa
++ nr_comp , DFSTRANSPUS ( *it ) ;
}
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 () ;
}