Pagini recente » Cod sursa (job #1210476) | Cod sursa (job #1652255) | Cod sursa (job #1892126) | Cod sursa (job #2365375) | Cod sursa (job #719993)
Cod sursa(job #719993)
#include<fstream>
#include<cstdio>
#include<vector>
#define INfile "ctc.in"
#define OUTfile "ctc.out"
#define pb push_back
#define NMAX 100001
using namespace std ;
ifstream F ( INfile ) ;
//ofstream G ( OUTfile ) ;
int N , M , ctc , nre ;
int viz [ NMAX ] , V [ NMAX ] ;
vector < int > V1 [ NMAX ] , V2 [ NMAX ] , SOL [ NMAX ] ;
void read () ;
void solve () ;
void write () ;
void DFS1 ( int k ) ;
void DFS2 ( int k ) ;
int main ()
{
read () ;
solve () ;
write () ;
F.close () ;
//G.close () ;
return 0 ;
}
void read ()
{
int i , x , y ;
F >> N >> M ;
for ( i = 1 ; i <= M ; ++ i )
{
F >> x >> y ;
V1 [ x ].pb ( y ) ;
V2 [ y ].pb ( x ) ;
}
}
void solve ()
{
int i ;
for ( i = 1 ; i <= N ; ++ i )
if ( ! viz [ i ] )
DFS1 ( i ) ;
for ( i = N ; i > 0 ; -- i )
if ( viz [ V [ i ] ] )
{
++ ctc ;
DFS2 ( V [ i ] ) ;
}
}
void DFS1 ( int k )
{
int i ;
viz [ k ] = 1 ;
for ( i = V1 [ k ].size () - 1 ; i > -1 ; --i )
if ( ! viz [ V1 [ k ][ i ] ] )
DFS1 ( V1 [ k ][ i ] ) ;
V [ ++ nre ] = k ;
}
void DFS2 ( int k )
{
int i ;
viz [ k ] = 0 ;
SOL [ ctc ].pb ( k ) ;
for ( i = V2 [ k ].size () - 1 ; i > -1 ; --i )
if ( viz [ V2 [ k ][ i ] ] )
DFS2 ( V2 [ k ][ i ] ) ;
}
void write ()
{
int i , j ;
freopen ( OUTfile , "w" , stdout ) ;
printf ( "%d\n" , ctc ) ;
for ( i = 1 ; i <= ctc ; ++ i )
{
for ( j = SOL [ i ].size () - 1 ; j > -1 ; -- j )
printf ( "%d " , SOL [ i ][ j ] );
printf( "\n" ) ;
}
}