Cod sursa(job #406777)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 1 martie 2010 19:50:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;

#define MAX_N 100005
#define MAX_S 10005

char s[ MAX_S ];
int xXx;
int N, M;
int cnt_s, ant[ MAX_N ];
bitset <MAX_N> f;
vector <int> sol[ MAX_N ], v_1[ MAX_N ], v_2[ MAX_N ];

inline void df_1( const int &nod ) {

    vector <int> :: iterator it;

    f[ nod ] = true;

    for( it = v_1[ nod ].begin(); it != v_1[ nod ].end(); ++it )
        if( f[ *it ] == false )
            df_1( *it );

    ant[ ++ant[ 0 ] ] = nod;
}

inline void df_2( const int &nod ) {

    vector <int> :: iterator it;

    f[ nod ] = false;
    sol[ xXx ].push_back( nod );

    for( it = v_2[ nod ].begin(); it != v_2[ nod ].end(); ++it )
        if( f[ *it ] == true )
            df_2( *it );
}

inline void read( int &val ) {

    while( !isdigit( s[ cnt_s ] ) )
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }

    val = 0;
    while( isdigit( s[ cnt_s ] ) ) {

        val = val*10 + s[ cnt_s ] - '0';
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }
    }
}

int main() {

    freopen( "ctc.in", "r", stdin );
    freopen( "ctc.out", "w", stdout );

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

    cnt_s = MAX_S - 1;

    read( N );
    read( M );

    while( M-- ) {

        read( x );
        read( y );

        v_1[ x ].push_back( y );
        v_2[ y ].push_back( x );
    }

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

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

            ++xXx;
            df_2( ant[ i ] );
        }

    printf( "%d\n", xXx );
    while( xXx ) {

        for( it = sol[ xXx ].begin(); it != sol[ xXx ].end(); ++it )
            printf( "%d ", *it );
        printf( "\n" );

        --xXx;
    }

    return 0;
}