Cod sursa(job #3177920)

Utilizator bombatongaMunteanu David Ioan bombatonga Data 30 noiembrie 2023 16:26:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
#include <bitset>

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

const int nMax = 1e5;

std::bitset<nMax> vis;

std::vector<std::vector<int>> Graph;

void dfs (int node) {
	vis[node] = 1;
	for (int i : Graph[node])
		if (!vis[i])
			dfs (i);
}
	
int main () {
	int N, M;
	fin >> N >> M;
	Graph.assign (N+1, std::vector<int>());
	for (int i = 1; i <= M; i++) {
		int x, y;
		fin >> x >> y;

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

	int nr = 0;
	for (int i = 1; i <= N; i++) {
		if (!vis[i]) {
			nr++;
			dfs(i);
		}
	}

	fout << nr;
	
	Graph.clear();
	fin.clear(); fout.clear();
	return 0;
}