Cod sursa(job #1993617)

Utilizator andrusca97Rosu Andrei andrusca97 Data 23 iunie 2017 13:29:58
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
/*
 * dfs.cpp
 *
 *  Created on: Jun 23, 2017
 *      Author: andreir
 */

#include <fstream>

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

int D[100005][100005], Vizitat[100005], N, M;


void Read() {
    int x, y;
    in >> N >> M;
    for (int i = 1; i <= M; i++) {
        in >> x >> y;
        D[x][y] = D[y][x] = 1;
    }
}

void dfs(int nod) {
    Vizitat[nod]=1;
    for(int i=1;i<=N;i++)
        if(Vizitat[i] == 0 && D[nod][i])
            dfs(i);
}

int main(){
    int k=0;
    Read();
    for(int i=1;i<=N;i++){
        if(Vizitat[i] == 0){
            dfs(i);
            k++;
        }
    }
    out<<k;
    return 0;
}