Cod sursa(job #849444)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 6 ianuarie 2013 22:43:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <cstdlib>
#include <vector>

#define nmax 500001

using namespace std;

vector<int> vecini[nmax];
int vizitat[nmax] , nr = 0 , N , M ;

void dfs ( int x )
{
    int y ;
    for ( int i = 0 ; i < vecini[x].size() ; i++ )
    {
        y = vecini[x][i];
        if ( !vizitat[y] )
            {
                vizitat[y] = 1;
                dfs ( y );
            }
    }
}

int main ()
{
    FILE *fin , *fout ;

    fin = fopen ( "dfs.in" , "rt" );
    fout = fopen ( "dfs.out" , "wt" );

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

    for ( int i = 1 ; i <= M ; i++ )
    {
        int a , b ;
        fscanf ( fin , "%d %d " , &a , &b ) ;
        vecini[a].push_back(b);
        vecini[b].push_back(a);
    }

    for ( int i = 1 ; i <= N ; i++ )
        if ( !vizitat[i] )
            {
                nr++;
                dfs ( i );
            }

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

    fclose ( fin );
    fclose ( fout  );

    return 0 ;

}