Cod sursa(job #591786)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 25 mai 2011 16:26:42
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <cstring>

#define NMAX 100001
#define pb push_back

using namespace std;

vector< int > G1[NMAX], G2[NMAX], New;
vector< vector< int > > CTC;
int N, M, i, x, y, Stack[NMAX];
bool USED[NMAX];

inline void DF( int Nod )
{
    USED[Nod] = true;

    for( vector< int >::iterator it = G1[Nod].begin(); it != G1[Nod].end(); it++ )
        if( !USED[*it] )
            DF( *it );

    Stack[ ++ Stack[0] ] = Nod;
}

inline void DFCTC( int Nod )
{
    USED[Nod] = false;
    New.pb( Nod );

    for( vector< int >::iterator it = G2[Nod].begin(); it != G2[Nod].end(); it++ )
        if( USED[*it] )
            DFCTC( *it );
}

int main()
{
    ifstream in("ctc.in");
    ofstream out("ctc.out");

    in >> N >> M;
    while( M-- )
    {
        in >> x >> y;
        G1[x].pb( y );
        G2[y].pb( x );
    }

    memset( USED, false, sizeof(USED) );
    Stack[0] = 0;
    for( i = 1; i <= N; i++ )
        if( !USED[i] )
            DF( i );

    for( i = N; i; i-- )
        if( USED[ Stack[i] ] )
        {
            New.erase( New.begin(), New.end() );
            DFCTC( Stack[i] );

            CTC.pb( New );
        }

    out << CTC.size() << '\n';
    for( int it = 0; it < (int)CTC.size(); it++ )
    {
        for( int it2 = 0; it2 < (int)CTC[it].size(); it2++ )
            out << CTC[it][it2] << ' ';
        out << '\n';
    }

    return 0;
}