Cod sursa(job #1504197)

Utilizator jimcarterJim Carter jimcarter Data 17 octombrie 2015 14:57:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>
using namespace std;

FILE *f = fopen ( "dfs.in" , "r" ) , *g = fopen ( "dfs.out" , "w" );

const int MAX = 100001;
int node1 , node2 , N , M , i , nrComp;
bool vis [ MAX ];
vector <int> edge [ MAX ];

void read()
{
    fscanf ( f , "%d %d" , &N , &M );
    for ( i = 1 ; i <= M ; i ++ )
    {
        fscanf ( f , "%d %d" , &node1 , &node2 );
        edge [ node1 ] . push_back ( node2 );
        edge [ node2 ] . push_back ( node1 );
    }
}

void dfs ( int node )
{
    vis [ node ] = true;
    for ( int i = 0 ; i < edge [ node ] . size() ; i ++ )
        if (vis [ edge [ node ] [ i ] ] == false )
            dfs ( edge [ node ] [ i ] );
}

int main()
{
    read();
    for ( i = 1 ; i <= N ; i ++ )
        if ( vis [ i ] == false )
        {
            nrComp ++;
            dfs ( i );
        }
    //print
    fprintf ( g , "%d\n" , nrComp );
    return 0;
}