Cod sursa(job #411279)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 4 martie 2010 20:10:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <algorithm>
#include <bitset>
using namespace std;

#define MAX_N 100005
#define MAX_S 10005

char s[ MAX_N ];
int N, M;
int cnt_s, nr_comp, r[ MAX_N ], t[ MAX_N ];
bitset <MAX_N> f;

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;
        }
    }
}

void unite( const int &nod_1, const int &nod_2 ) {

    if( r[ nod_1 ] < r[ nod_2 ] )
        t[ nod_1 ] = nod_2;
    else
        t[ nod_2 ] = nod_1;

    if( r[ nod_1 ] == r[ nod_2 ] )
        ++r[ nod_1 ];
}

int find( const int &nod ) {

    if( nod != t[ nod ] )
        t[ nod ] = find( t[ nod ] );

    return t[ nod ];
}

int main() {

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

    int i, x, y;

    cnt_s = MAX_S - 1;
    nr_comp = 0;

    read( N );
    read( M );

    for( i = 1; i <= N; ++i )
        t[ i ] = i;

    while( M-- ) {

        read( x );
        read( y );

        unite( find( x ), find( y ) );
    }

    for( i = 1; i <= N; ++i )
        f[ find( i ) ] = true;

    for( i = 1; i <= N; ++i )
        if( f[ i ] == true )
            ++nr_comp;

    printf( "%d", nr_comp );

    return 0;
}