Pagini recente » Cod sursa (job #1528468) | Cod sursa (job #384094) | Cod sursa (job #1922746) | Cod sursa (job #3128468) | Cod sursa (job #1712737)
#include <cstdio>
#include <vector>
#include <bitset>
#include <deque>
#include <algorithm>
const int SIZE = 100000;
const int INFI = 2000000000;
int nr_nodes, nr_edges, nr_components, cursor, node1, node2;
int lower[SIZE], level[SIZE]; std::bitset <SIZE> marked, in_stack;
std::vector <int> edge[SIZE], component[SIZE]; std::deque <int> my_stack;
inline void dfs( int node ) {
my_stack.push_back( node );
marked[node] = in_stack[node] = 1;
lower[node] = level[node] = ++cursor;
std::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( in_stack[next_node] )
lower[node] = std::min( lower[node], lower[next_node] );
}
if( lower[node] == level[node] ) {
nr_components ++;
int aux_node;
do {
aux_node = my_stack.back();
my_stack.pop_back(); in_stack[aux_node] = 0;
component[nr_components].push_back(aux_node);
} while( aux_node != node );
}
return;
}
int main( int argc, const char *argv[] ) {
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 ++ ) {
std::sort( component[i].begin(), component[i].end() );
std::vector <int> :: iterator it;
for( it = component[i].begin(); it != component[i].end(); it ++ ) {
int next_node = *it;
printf( "%d ", next_node );
}
printf( "\n" );
}
return 0;
}