Cod sursa(job #2358878)

Utilizator Reznicencurol.tester Reznicencu Data 28 februarie 2019 13:50:58
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <vector>
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <string.h>

#define SZ 1000

void addMuchie(std::vector<int> graf[], int m1, int m2) {
	graf[m1].push_back(m2);
	graf[m2].push_back(m1);
}

void dfs(std::vector <int> graf[], bool viz[], int nod) {
	viz[nod] = true;

	int lim = graf[nod].size();

	for (size_t i = 0; i < lim; i++) {
		int vecin = graf[nod][i];

		if (!viz[vecin])
			dfs(graf, viz, vecin);
	}
}

int main() {
	std::ifstream gfile("dfs.in");
	std::ofstream gFileOut("dfs.out");

	size_t n, m, nd, nd1, cmpConexe = 0;

	gfile >> n >> m;

	std::vector<int> graf[SZ];

	bool viz[SZ];

	memset(viz, 0, SZ);

	for (size_t i = 0; i < m; i++) {
		gfile >> nd >> nd1;

		addMuchie(graf, nd, nd1);
	}

	for (size_t i = 0; i < n; i++) {
		if (!viz[i]) {
			dfs(graf, viz, i);
			cmpConexe++;
		}
	}

	gFileOut << cmpConexe;

	return 0;
}