Cod sursa(job #2293276)

Utilizator VadimCCurca Vadim VadimC Data 30 noiembrie 2018 19:01:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define NMax 100010

int n, m;
vector<int> a[NMax];
vector<bool> viz(NMax, false);
int nrc;

void citire();
void dfs(int);

int main(){
	citire();
	for(int i = 1; i <= n; i++)
		if(!viz[i]){
			nrc++;
			dfs(i);
		}
	fout << nrc;
}

void citire(){
	int x, y;
	fin >> n >> m;
	while(m--){
		fin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
}

void dfs(int x){
	viz[x] = true;
	for(int i = 0; i < a[x].size(); i++)
		if(!viz[a[x][i]]) dfs(a[x][i]);
}