Cod sursa(job #1494209)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 30 septembrie 2015 20:22:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include<vector>

using namespace std;

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

const int nmax = 100000;
int f[ nmax + 1 ];
vector< int > ord;
vector< int > gp[ nmax + 1 ], gm[ nmax + 1 ];
vector< int > c;
vector< vector< int > > C;

void dfs_plus( int nod ) {
    f[ nod ] = 1;

    for( vector< int >::iterator it = gp[ nod ].begin(); it != gp[ nod ].end(); ++ it ) {
        if ( f[ *it ] == 0 ) {
            dfs_plus( *it );
        }
    }
    ord.push_back( nod );
}
void dfs_minus( int nod ) {
    c.push_back( nod );
    f[ nod ] = 2;

    for( vector< int >::iterator it = gm[ nod ].begin(); it != gm[ nod ].end(); ++ it ) {
        if ( f[ *it ] == 1 ) {
            dfs_minus( *it );
        }
    }
}
int main() {
    int n, m, x, y;
    fin >> n >> m;
    for( int i = 0; i < m; ++ i ) {
        fin >> x >> y;
        gp[ x ].push_back( y );
        gm[ y ].push_back( x );
    }

    for( int i = 1; i <= n; ++ i ) {
        if ( f[ i ] == 0 ) {
            dfs_plus( i );
        }
    }
    for( int i = ( int )ord.size() - 1; i >= 0; -- i ) {
        if ( f[ ord[ i ] ] == 1 ) {
            c.clear();
            dfs_minus( ord[ i ] );
            C.push_back( c );
        }
    }

    fout << ( int )C.size() << "\n";
    for( int i = 0; i < ( int )C.size(); ++ i ) {
        for( vector< int >::iterator it = C[ i ].begin(); it != C[ i ].end(); ++ it ) {
            fout << *it << " ";
        }
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}