Cod sursa(job #1890482)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 23 februarie 2017 12:09:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

#define NMAX 100005
stack < int > Q;
vector < int > v[ NMAX ];
vector < vector < int > > sol;

int lowBound[ NMAX ];
int upBound[ NMAX ];
int inStack[ NMAX ];
int pas;

void CTC ( int nod ) {

    int i, j, k;
    vector < int > aux;
    vector < int > :: iterator it;

    lowBound[ nod ] = upBound[ nod ] = ++pas;
    inStack[ nod ] = 1;
    Q.push( nod );

    for ( it = v[ nod ].begin(); it != v[ nod ].end(); ++it ) {
        if ( !lowBound[ *it ] ) {
            CTC( *it );
            lowBound[ nod ] = min ( lowBound[ nod ], lowBound[ *it ] );
        } else if ( inStack[ *it ] ){
            lowBound[ nod ] = min ( lowBound[ nod ], lowBound[ *it ] );
        }

    }

    if ( lowBound[ nod ] == upBound[ nod ] ) {
        aux.clear();
        do {
            k = Q.top();
            Q.pop();
            aux.push_back( k );
            inStack[ k ] = 0;
        } while ( k != nod );
        aux.push_back( -1 );
        sol.push_back( aux );
    }

}

int main () {

    freopen( "ctc.in", "r", stdin );
    freopen( "ctc.out", "w", stdout );

    int n, m, i, j, x, y;

    scanf( "%d%d",&n,&m );
    while ( m-- ) {
        scanf( "%d%d",&x,&y );
        v[ x ].push_back( y );
    }

    for ( i = 1; i <= n; ++i ) {
        if ( !lowBound[ i ] ) CTC( i );
    }

    m = sol.size();
    printf( "%d\n",m );

    for ( i = 0; i < m; ++i ) {
        sort ( sol[ i ].begin(), sol[ i ].end() );
        for ( j = 1; j < sol[ i ].size(); ++j ) {
            if ( sol[ i ][ j ] != sol[ i ][ j - 1 ] )
                printf( "%d ",sol[ i ][ j ] );
        }
        printf( "\n" );
    }

    return 0;

}