Pagini recente » Cod sursa (job #1364271) | Cod sursa (job #2969739) | Cod sursa (job #1009736) | Cod sursa (job #1883253) | Cod sursa (job #1651682)
#include <bits/stdc++.h>
const int DIM = 1 << 17;
using namespace std;
int node1, node2, node, nr_nodes, Level[DIM];
int current_level, nr_components, nr_edges, Lower[DIM];
bitset <DIM> Marked, InStack; deque <int> Stack;
vector <int> Edge[DIM], Component[DIM];
void DFS( int node ) {
Stack.push_back( node );
Marked[node] = InStack[node] = 1;
Level[node] = Lower[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] )
Lower[node] = min( Lower[node], Lower[next_node] );
}
if( Lower[node] == Level[node] ) {
nr_components ++;
int aux_node;
do {
aux_node = Stack.back();
Stack.pop_back(); InStack[aux_node] = 0;
Component[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 ++ ) {
vector <int> :: iterator it;
for( it = Component[i].begin(); it != Component[i].end(); it ++ ) {
node = *it;
printf( "%d ", node );
}
printf( "\n" );
}
return 0;
}