Cod sursa(job #1611703)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 24 februarie 2016 12:53:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#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;
}