Pagini recente » Cod sursa (job #2515848) | Cod sursa (job #2483014) | Cod sursa (job #2149433) | Cod sursa (job #1328504) | Cod sursa (job #1457736)
#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;
}