Cod sursa(job #1382717)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 9 martie 2015 15:04:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );

const int nmax = 100000;
int ii;
int index[ nmax + 1 ], lowlink[ nmax + 1 ];
bool in_stiva[ nmax + 1 ];
vector< int > g[ nmax + 1 ], c;
vector< vector< int > > C;
stack< int > st;

inline int min2( int a, int b ) {
    if ( a < b ) {
        return a;
    }
    return b;
}
void tarjan( int nod ) {
    index[ nod ] = ii;
    lowlink[ nod ] = ii;
    ++ ii;
    st.push( nod );
    in_stiva[ nod ] = 1;

    for( vector< int >::iterator it = g[ nod ].begin(); it != g[ nod ].end(); ++ it ) {
        if ( index[ *it ] == -1 ) {
            tarjan( *it );
            lowlink[ nod ] = min2( lowlink[ *it ], lowlink[ nod ] );
        } else if ( in_stiva[ *it ] == 1 ) {
            lowlink[ nod ] = min2( lowlink[ *it ], lowlink[ nod ] );
        }
    }

    if ( index[ nod ] == lowlink[ nod ] ) { /// este radacina
        c.clear();
        int k;
        do {
            k = st.top(); st.pop();
            in_stiva[ k ] = 0;
            c.push_back( k );
        } while ( k != nod );
        C.push_back( c );
    }
}
int main() {
    int n, m, x, y;
    fin >> n >> m;
    for( int i = 0; i < m; ++ i ) {
        fin >> x >> y;
        g[ x ].push_back( y );
    }
    for( int i = 1; i <= n; ++ i ) {
        index[ i ] = -1;
    }
    ii = 1;
    for( int i = 1; i <= n; ++ i ) {
        if ( index[ i ] == -1 ) {
            tarjan( i );
        }
    }
    fout << C.size() << "\n";
    for( int i = 0; i < ( int )C.size(); ++ i ) {
        for( int j = 0; j < ( int )C[ i ].size(); ++ j ) {
            fout << C[ i ][ j ] << " ";
        }
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}