Pagini recente » Cod sursa (job #1053097) | Cod sursa (job #2550510) | Cod sursa (job #2762713) | Cod sursa (job #1914650) | Cod sursa (job #1816118)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <list>
using namespace std ;
ifstream f("ctc.in") ;
ofstream g("ctc.out") ;
const int Nmax = 100001 ;
vector <int> G[Nmax] , Gt[Nmax] ;
vector <int> Viz ;
int n , m , current_node ;
list <int> s ;
vector <int> Sol[Nmax] ;
void read()
{
f >> n >> m ;
for ( int cnt = 1 ; cnt <= m ; ++cnt )
{
int x , y ;
f >> x >> y ;
G[x].push_back (y) ;
Gt[y].push_back (x) ;
}
}
void dfs ( int x )
{
Viz[x] = 1 ;
for ( const int & y : G[x] )
{
if ( Viz[y] ) continue ;
dfs (y) ;
}
s.push_front(x) ;
}
void dfsGT ( int x )
{
Viz[x] = 1 ;
for ( const int & y : Gt[x] )
{
if ( Viz[y] ) continue ;
dfsGT (y) ;
}
Sol[current_node].push_back (x) ;
}
int main ()
{
read () ;
Viz.resize ( n + 1 );
for ( int i = 1 ; i <= n ; ++i )
if ( Viz[i] == 0 )
dfs (i) ;
int cnt_comp_conexe = 0 ;
Viz = vector <int> () ;
Viz.resize(n + 1) ;
for ( const int & y : s )
if ( Viz[y] == 0 )
{
++cnt_comp_conexe ;
current_node = y ;
dfsGT (y) ;
}
g << cnt_comp_conexe << '\n' ;
for ( int i = 1 ; i <= n ; ++i )
{
if ( !Sol[i].empty ())
{
for ( const int & y : Sol[i] )
g << y << " " ;
g << "\n" ;
}
}
}