Cod sursa(job #2255926)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 7 octombrie 2018 18:37:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

#define NMAX 100005

int nr, pas, U[ NMAX ], D[ NMAX ], InStack[ NMAX ];
stack < int > Q;
vector < int > V[ NMAX ], S[ NMAX ];

void tarjan( int nod ) {

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

    Q.push( nod );
    InStack[ nod ] = 1;
    U[ nod ] = D[ nod ] = ++pas;


    for ( it = V[ nod ].begin(); it != V[ nod ].end(); ++it ) {
        fiu = *it;
        if ( U[ fiu ] == 0 ) {
            tarjan( fiu );
            D[ nod ] = min( D[ nod ], D[ fiu ] );
        } else if ( InStack[ fiu ] ) {
            D[ nod ] = min( D[ nod ], D[ fiu ] );
        }
    }


    if ( U[ nod ] == D[ nod ] ) {
        nr++;
        do {
            S[ nr ].push_back( fiu = Q.top() );
            Q.pop();
            InStack[ fiu ] = 0;

        } while ( fiu != nod );
    }


}

int main () {

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

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

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

    for ( i = 1; i <= n; ++i ) {
        if ( U[ i ] == 0 ) tarjan( i );
    }

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

    return 0;

}