Cod sursa(job #2986377)

Utilizator the_horoHorodniceanu Andrei the_horo Data 28 februarie 2023 14:20:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <array>
#include <fstream>
#include <vector>


std::array<bool, 100010> viz;
std::array<std::vector<int>, 100010> edges;


void dfs (int node) {
	viz[node] = true;

	for (auto to: edges[node])
		if (!viz[to])
			dfs(to);
}

int main () {
	std::ifstream  in("dfs.in");   in.exceptions(in.failbit);
	std::ofstream out("dfs.out"); out.exceptions(out.failbit);

	int n, m;
	in >> n >> m;

	for (int i = 0; i < m; ++ i) {
		int x, y;
		in >> x >> y;

		edges[x].emplace_back(y);
		edges[y].emplace_back(x);
	}

	int result = 0;
	for (int i = 1; i <= n; ++ i)
		if (!viz[i]) {
			dfs(i);
			++ result;
		}

	out << result << '\n';
}