Cod sursa(job #1707051)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 24 mai 2016 06:20:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <deque>
#include <algorithm>

const int SIZE = 1e5 + 5;
const int INFI = 0x3f3f3f3f;

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;
}