Pagini recente » Cod sursa (job #2271570) | Cod sursa (job #2982076) | Cod sursa (job #1566387) | Cod sursa (job #460615) | Cod sursa (job #1520594)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
FILE *f = fopen ( "ctc.in" , "r" ) , *g = fopen ( "ctc.out" , "w" );
const int MAX = 100005;
int N , M , i , j , x , y , nrComp , node;
bool visited [ MAX ];
vector < int > edge [ MAX ] , edgeT [ MAX ] , sccs [ MAX ];
stack < int > finish;
void read()
{
fscanf ( f , "%d %d" , &N , &M );
for ( i = 1 ; i <= M ; i ++ )
{
fscanf ( f , "%d %d" , &x , &y );
edge [ x ] . push_back ( y );
edgeT [ y ] . push_back ( x );
}
}
void dfs ( int node )
{
visited [ node ] = true;
for ( int i = 0 ; i < edge [ node ] . size() ; i ++ )
if ( !visited [ edge [ node ] [ i ] ] )
dfs ( edge [ node ] [ i ] );
finish . push ( node );
}
void dfsT ( int node )
{
visited [ node ] = false;
sccs [ nrComp ] . push_back ( node );
for ( int i = 0 ; i < edgeT [ node ] . size() ; i ++ )
if ( visited [ edgeT [ node ] [ i ] ] )
dfsT ( edgeT [ node ] [ i ] );
}
void scc()
{
for ( i = 1 ; i <= N ; i ++ )
if ( !visited [ i ] )
dfs ( i );
while ( !finish.empty() )
{
node = finish . top() , finish . pop();
if ( visited [ node ] )
{
nrComp ++;
dfsT ( node );
}
}
}
void print()
{
fprintf ( g , "%d\n" , nrComp );
for ( i = 1 ; i <= nrComp ; i ++ )
{
for ( j = 0 ; j < sccs [ i ] . size() ; j ++ )
fprintf ( g , "%d " , sccs [ i ] [ j ] );
fprintf ( g , "\n" );
}
}
int main()
{
read();
scc();
print();
return 0;
}