Cod sursa(job #554100)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 14 martie 2011 16:57:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <algorithm>
#include <bitset>
#include <fstream>
#include <vector>

using namespace std;

const char Input[] = "ctc.in";
const char Output[] = "ctc.out";

const int Dim = 100001;

int N, M;
int ncomp, ant[Dim];
bitset <Dim> f;
vector <int> v[Dim], vt[Dim], comp[Dim];

void DF( int nod ) {

    vector <int> :: iterator it;

    f[nod] = true;
    for( it = v[nod].begin(); it != v[nod].end(); ++it )
        if( f[*it] == false )
            DF( *it );
    ant[++ant[0]] = nod;
}

void DFT( int nod ) {

    vector <int> :: iterator it;

    f[nod] = false;
    comp[ncomp].push_back( nod );
    for( it = vt[nod].begin(); it != vt[nod].end(); ++it )
        if( f[*it] == true )
            DFT( *it );
}

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int i, x, y;
    vector <int> :: iterator it;

    fin >> N >> M;
    while( M-- ) {

        fin >> x >> y;
        v[x].push_back( y );
        vt[y].push_back( x );
    }

    for( i = 1; i <= N; ++i )
        if( f[i] == false )
            DF( i );

    for( i = N; i >= 1; --i )
        if( f[ant[i]] == true ) {

            ++ncomp;
            DFT( ant[i] );
        }

    fout << ncomp << "\n";
    for( i = 1; i <= ncomp; fout << "\n", ++i )
        for( it = comp[i].begin(); it != comp[i].end(); ++it )
            fout << *it << " ";

    fin.close();
    fout.close();

    return 0;
}