Pagini recente » Cod sursa (job #2195609) | Cod sursa (job #1171762) | Cod sursa (job #2498695) | Cod sursa (job #909482) | Cod sursa (job #1338012)
#include <algorithm>
#include <fstream>
#include <vector>
#include <iostream>
#include <stack>
#include <cstring>
#define NMAX 100005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in ( "ctc.in" );
ofstream out ( "ctc.out" );
vector < int > G[NMAX] , GT[NMAX] , Sol[NMAX];
int Answer , N , M ;
bool used[NMAX];
stack < int > S ;
void DFP ( int node ){
used[node] = true ;
for ( vector < int > ::iterator it = G[node].begin() ; it != G[node].end() ; ++it )
if ( !used[*it] )
DFP(*it);
S.push(node);
}
void DFM ( int node ){
Sol[Answer].push_back( node );
used[node] = true ;
for ( vector < int > ::iterator it = GT[node].begin() ; it != GT[node].end() ; ++it )
if ( !used[*it] )
DFM(*it);
}
void DoKosaraju ( void ){
int i , j ;
for ( i = 1 ; i <= N ; ++i )
if( !used[i] )
DFP(i);
memset ( used , false , sizeof(used));
while( ! S.empty()){
int node = S.top();
S.pop();
if ( !used[node]){
++Answer;
DFM(node);
}
}
return ;
}
int main ( void ){
int i , j ;
in >> N >> M ;
for ( i = 1 ; i <= M ; ++i ){
int x , y;
in >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
DoKosaraju();
out << Answer << "\n";
for ( i = 1 ; i <= Answer ; ++i ){
for ( vector < int > ::iterator it = Sol[i].begin() ; it!= Sol[i].end() ; ++it )
out << *it << " ";
out << "\n";
}
return 0 ;
}