Cod sursa(job #3293972)

Utilizator solotpaulSolot Paul solotpaul Data 14 aprilie 2025 17:05:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;

void dfs(int source, vector<bool>& visited, vector<list<int>>& v) {
	if (visited[source]) {
		return;
	}
	visited[source] = true;
	for (const auto& el : v[source]) {
		dfs(el, visited, v);
	}
}

int main() {
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	int n, m;
	fin >> n >> m;
	vector<list<int>> v(n + 1);
	for (int i = 0; i < m; ++i) {
		int x, y;
		fin >> x >> y;
		v[x].push_front(y);
		v[y].push_front(x);
	}
	vector<bool> visited(n + 1, false);
	int count = 0;
	for (int i = 1; i <= n; ++i) {
		if (!visited[i]) {
			count++;
			dfs(i, visited, v);
		}
	}
	fout << count << '\n';
	return 0;
}