Cod sursa(job #1725603)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 6 iulie 2016 00:06:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 100005
#define INFI 0x3f3f3f

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

int pas;
int upBound[ NMAX ];
int in_stack[ NMAX ];
int lowBound[ 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( !upBound[ i ] ) tarjan( i );

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

    for( i = 0; i < s; ++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, t, fiu;

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

    for( int fiu : v[ nod ] ){
        if( !lowBound[ fiu ] ){
            tarjan( fiu );
            lowBound[ nod ] = minim( lowBound[ nod ], lowBound[ fiu ] );
        }
        else if( in_stack[ fiu ] )
            lowBound[ nod ] = minim( lowBound[ nod ], lowBound[ fiu ] );
    }

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

}


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