Pagini recente » Diferente pentru olimpici intre reviziile 180 si 141 | Cod sursa (job #1122807) | Monitorul de evaluare | Atasamentele paginii miercuri_ora_9.00 | Cod sursa (job #1457751)
#include <iostream>
#include <fstream>
#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] ; // 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 ;
}
vector <int> sol [100001] ;
int nr_comp ;
void DFSTRANSPUS ( int nd )
{
vizt [nd] = 1 ;
nod * p ;
sol [ nr_comp ].push_back ( nd ) ;
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 )
DFS (i) ;
for ( i = nr_t ; i >= 1 ; -- i )
{
if ( vizt [ timp[i] ] == 0 ) // nu face parte inca din nicio comp conexa
++ nr_comp , DFSTRANSPUS ( timp [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 () ;
return 0;
}