Pagini recente » Cod sursa (job #2469451) | Istoria paginii runda/dedicatie_speciala5 | Cod sursa (job #907351) | Cod sursa (job #1248555) | Cod sursa (job #1458002)
#include <iostream>
#include <fstream>
#include <vector>
#define minim(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
ifstream fin ("ctc.in") ;
ofstream fout ("ctc.out") ;
int N , M ;
struct nod
{
nod * next ;
int info ;
} ;
nod * L[100001] ; // L = lista noduri adiacente pt fiecare
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 ;
}
int idx [100001] , lowlink [100001] , stiva [100001] , index , top_s , nr_comp , node ;
vector < int > sol [100001] ;
bool in_stiva [100001] ;
void TarjanDFS ( int nd )
{
idx [ nd ] = index ;
lowlink [ nd ] = index ;
++ index ;
stiva [ ++ top_s ] = nd ;
in_stiva [ nd ] = 1 ;
nod * p ;
for ( p = L [ nd ] ; p != 0 ; p = p->next )
{
if ( idx [ p->info ] == -1 )
TarjanDFS ( p->info ) , lowlink [ nd ] = minim(lowlink [ nd ] , lowlink [ p->info ]) ;
else if ( in_stiva [ p->info ] == 1 )
lowlink [ nd ] = minim(lowlink [ nd ] , lowlink [ p->info ]) ;
}
if ( lowlink [ nd ] == idx [ nd ] )// este nd radacina a unei componente conexe
{
++ nr_comp ;
do
{
sol [ nr_comp ] .push_back ( ( node = stiva [ top_s ] ) ) ;
in_stiva [ node ] = 0 ;
-- top_s ;
}
while ( nd != node ) ;
}
}
void CompTareConexe ()
{
int i ;
for ( i = 1 ; i <= N ; ++ i )
idx [i] = -1 ;
for ( i = 1 ; i <= N ; ++ i )
if ( idx [i] == -1 )
TarjanDFS (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 () ;
CompTareConexe () ;
return 0 ;
}