Pagini recente » Cod sursa (job #1108741) | Istoria paginii runda/sim_10_2016_2/clasament | Cod sursa (job #1869434) | Cod sursa (job #1611703)
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#include <deque>
const int DIM = 1 << 17;
using namespace std;
int nr_nodes, nr_edges, node1, node2, current_level, nr_components;
vector <int> Edge[DIM], MyComponent[DIM]; int Low[DIM], Lev[DIM];
bitset <DIM> Marked, InStack; deque <int> Stack;
void DFS( int node ) {
Stack.push_back( node );
Marked[node] = InStack[node] = 1;
Low[node] = Lev[node] = ++current_level;
vector <int> :: iterator it;
for( it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
int next_node = *it;
if( !Marked[next_node] )
DFS( next_node );
if( InStack[next_node] )
Low[node] = min( Low[node], Low[next_node] );
}
if( Low[node] == Lev[node] ) {
nr_components ++;
int aux_node;
do {
aux_node = Stack.back();
Stack.pop_back(); InStack[aux_node] = 0;
MyComponent[nr_components].push_back( aux_node );
} while( aux_node != node );
}
return;
}
int main () {
freopen( "ctc.in" , "r", stdin );
freopen( "ctc.out", "w", stdout );
scanf( "%d %d", &nr_nodes, &nr_edges );
for( int i = 1; i <= nr_edges; i ++ ) {
scanf( "%d %d", &node1, &node2 );
Edge[node1].push_back( node2 );
}
for( int i = 1; i <= nr_nodes; i ++ ) {
if( !Marked[i] )
DFS( i );
}
printf( "%d\n", nr_components );
for( int i = 1; i <= nr_components; i ++ ) {
for( int j = 0; j < MyComponent[i].size(); j ++ )
printf( "%d ", MyComponent[i][j] );
printf( "\n" );
}
return 0;
}