Cod sursa(job #1911244)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 7 martie 2017 19:51:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;

#define NMAX 100005

int LowBound[ NMAX ];
int UpBound[ NMAX ];

int inS[ NMAX ];
int pas;

stack < int > S;
vector < int > aux;
vector < int > V[ NMAX ];
vector < vector < int > > Sol;

void Tarjan ( int nod ) {

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

    LowBound[ nod ] = UpBound[ nod ] = ++pas;
    S.push( nod ); inS[ nod ] = 1;

    for ( it = V[ nod ].begin(); it != V[ nod ].end(); ++it ) {
        fiu = *it;
        if ( !LowBound[ fiu ] ) {
            Tarjan( fiu );
            LowBound[ nod ] = min( LowBound[ nod ], LowBound[ fiu ] );
        } else if ( inS[ fiu ] ) {
            LowBound[ nod ] = min( LowBound[ nod ], LowBound[ fiu ] );
        }
    }

    if ( LowBound[ nod ] == UpBound[ nod ] ) {
        aux.clear();
        do {
            aux.push_back( t = S.top() );
            inS[ t ] = 0;
            S.pop();

        } while ( t != nod );
        Sol.push_back( aux );
    }

}

int main () {

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

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

    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 ] ) Tarjan( i );
    }

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

    return 0;

}