Cod sursa(job #1651682)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 13 martie 2016 18:35:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#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;
}