Cod sursa(job #2251583)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 1 octombrie 2018 19:20:59
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;

#define NMAX 100005

int NrComp, pas, Up[ NMAX ], Down[ NMAX ], InS[ NMAX ];
vector < int >  V[ NMAX ];
vector < int > Sol[ NMAX ];
stack < int > Q;

void Tarjan ( int nod ) {

    int i, j, fiu;
    vector < int > :: iterator it;

    Up[ nod ] = Down[ nod ] = ++pas;
    InS[ nod ] = 1;
    Q.push( nod );

    for ( it = V[ nod ].begin(); it != V[ nod ].end(); ++it ) {
        fiu = *it;
        if ( !Up[ fiu ] ) {
            Tarjan( fiu );
            Down[ nod ] = min( Down[ nod ], Down[ fiu ] );
        } if ( InS[ fiu ] ) {
            Down[ nod ] = min( Down[ nod ], Down[ fiu ] );
        }
    }

    if ( Up[ nod ] == Down[ nod ] ) {
        ++NrComp;
        do {
            fiu = Q.top();
            Q.pop();
            InS[ fiu ] = 0;
            Sol[ NrComp ].push_back( fiu );
        } while ( fiu != nod );
    }


}


int main () {

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

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

    scanf( "%d%d", &n, &m );

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

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

    printf( "%d\n", NrComp );
    for ( i = 1; i <= NrComp; ++i ) {
        sort( Sol[ i ].begin(), Sol[ i ].end() );
        for ( j = 0; j < Sol[ i ].size(); ++j ) {
            printf( "%d ", Sol[ i ][ j ] );
        }
        printf( "\n" );
    }

    return 0;
}