Cod sursa(job #1657134)

Utilizator felixiPuscasu Felix felixi Data 20 martie 2016 10:30:15
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int NMAX = 100000;

bool viz[NMAX+2];
vector <int> G[NMAX+2], GP[NMAX+2], ord, ind_ctc;
int N, M;
vector < vector<int> > ctc;

void Dfs_Plus( int nod ) {
    viz[nod] = 1;
    ord.push_back( nod );

    for( int i = 0;  i < (int)GP[nod].size();  ++i ) {
        int x = GP[nod][i];
        if( !viz[x] )  {
            Dfs_Plus( x );
        }
    }
}

void Dfs_Minus( int nod ) {
    viz[nod] = 1;
    ind_ctc.push_back( nod );

    for( int i = 0;  i < (int)G[nod].size();  ++i ) {
        int x = G[nod][i];
        if( !viz[x] ) {
            Dfs_Minus( x );
        }
    }
}

int main() {
    in >> N >> M;
    for( int i = 1;  i <= M;  ++i ) {
        int x,y;
        in >> x >> y;
        G[x].push_back( y );
        GP[y].push_back( x );
    }

    for( int i = 1;  i <= N;  ++i ) {
        if( !viz[i] )  Dfs_Plus(i);
    }
    memset( viz, 0, sizeof(viz) );
    for( int i = (int)ord.size() - 1;  i >= 0;  --i ) {
        if( !viz[ ord[i] ] )  {
            ind_ctc.clear();

            Dfs_Minus( ord[i] );

            sort( ind_ctc.begin(), ind_ctc.end() );
            ctc.push_back( ind_ctc );
        }
    }

    out << (int)ctc.size() << '\n';
    for( int i = 0;  i < (int)ctc.size();  ++i ) {
        for( int j = 0;  j < (int)ctc[i].size();  ++j )  out << ctc[i][j] << ' ';
        out << '\n';
    }

    return 0;
}