Cod sursa(job #3262262)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 9 decembrie 2024 16:42:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

int main() {

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

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

	vector<vector<int>> g(n + 1);
	for(int i =1 ; i <= m; i++) {
		int x, y;
		in >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}	

	vector<bool> seen(n + 1);
	function<void(int)> dfs = [&](int node) {
		seen[node] = true;
		for(auto son : g[node]) {
			if(seen[son]) { continue; }
			dfs(son);
		}
	};

	int connected_components = 0;
	for(int i = 1; i <= n; i++) {
		if(seen[i]) { continue; }
		dfs(i);
		connected_components++;
	}

	out << connected_components << '\n';

	return 0;
}