Cod sursa(job #1712737)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 3 iunie 2016 16:21:10
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#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;
}