Cod sursa(job #1725406)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 5 iulie 2016 17:13:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 100005
#define INFI 0x3f3f3f3

stack < int > Q;
vector < int > aux;
vector < int > v[ NMAX ];
vector < vector <int > > sol;

int pas;
int vizt[ NMAX ];
int lowBound[ NMAX ];
int upBound[ NMAX ];
int in_stack[ NMAX ];

void tarjan( int nod );
int minim( int a, int b );

int main()
{

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

    int n, m, i, j, x, y, s, t, 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( !vizt[ i ] ) tarjan( i );

    printf("%d\n",sol.size());
    for( i = 0; i < sol.size(); ++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;

}

void tarjan( int nod ){

    int i, j, ok, fiu;

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

    for( i = 0; i < v[ nod ].size(); ++i ){
        fiu = v[ nod ][ i ];
        if( !vizt[ fiu ] ){
            tarjan( fiu );
            lowBound[ nod ] = minim( lowBound[ nod ], lowBound[ fiu ] );
        }
        else if( in_stack[ v[ nod ][ i ] ] )
            lowBound[ nod ] = minim( lowBound[ nod ], lowBound[ fiu ] );
    }

    if( lowBound[ nod ] == upBound[ nod ] ){
        ok = 0;
        aux.clear();
        while( !ok ){
            aux.push_back( Q.top() );
            in_stack[ Q.top() ] = 0;
            ok = ( nod == Q.top() );
            Q.pop();
        }
        sol.push_back( aux );
    }

}


int minim( int a, int b ){
    if( a > b ) return b;
    return a;
}