Cod sursa(job #1117946)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 23 februarie 2014 21:18:35
Problema Parcurgere DFS - componente conexe Scor 15
Compilator c Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>

#define N_MAX 100000
#define M_MAX 200000
typedef char bool;

int list[ M_MAX + 1 ], next[ M_MAX + 1 ], beg[ N_MAX + 1 ], end[ N_MAX + 1 ], sp;
bool seen[ N_MAX + 1 ];

void add( int n1, int n2 ) {
    list[ ++ sp ] = n2;
    if( beg[ n1 ] ) {
        next[ end[ n1 ] ] = sp;
        end[ n1 ] = sp;
    } else {
        beg[ n1 ] = end[ n1 ] = sp;
    }
}

void DFS( int node ) {
    if( !seen[ node ] ) {
        seen[ node ] = 1;
        int curr = beg[ node ];
        while( curr ) {
            DFS( list[ curr ] );
            curr = next[ curr ];
        }
    }
}

int main( ) {
    FILE * fin, * fout;
    fin = fopen( "dfs.in", "r" );
    fout = fopen( "dfs.out", "w" );

    int N, M;
    fscanf( fin, "%d%d", &N, &M );

    int i;
    for( i = 1; i <= M; i ++ ) {
        int n1, n2;
        fscanf( fin, "%d%d", &n1, &n2 );
        add( n1, n2 );
    }

    int num = 0;
    for( i = 1; i <= N; i ++ ) {
        if( !seen[ i ] ) {
            num ++;
            DFS( i );
        }
    }

    fprintf( fout, "%d\n", num );

    fclose( fin );
    fclose( fout );
}