Cod sursa(job #1435433)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 13 mai 2015 08:52:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define DIM 100010
using namespace std;

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

int Frec[DIM], N, M, nr, X, Y;
vector<int> V[DIM];

void SetUp(){
    fscanf(fin, "%d %d ",  &N, &M);
    for(int i = 1; i <= M; i ++){
        fscanf(fin, "%d %d ", &X, &Y);
        V[X].push_back(Y);
        V[Y].push_back(X);
    }
    return;
}

void DFS(int A[], int pos){
    A[pos] = 1;
    for(int i = 0; i < V[pos].size(); i ++)
        if(Frec[V[pos][i]] == 0)
            DFS(A, V[pos][i]);
    return;
}

void CodeExpert(){
    for(int i = 1; i <= N; i ++){
        if(Frec[i] == 0){
            nr ++;
            DFS(Frec, i);
        }
    }
    fprintf(fout, "%d\n", nr);
    return;
}

int main(){
    SetUp();
    CodeExpert();
    return 0;
}