Cod sursa(job #3361578)

Utilizator MihaiDraghiciMIHAI DRAGHICI MihaiDraghici Data 25 iulie 2026 20:34:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <vector>

using namespace std;

vector<vector<int>> graf;
vector<bool> viz;

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

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

	for (int i = 0; i < graf[poz].size(); i++) {

		int vecin = graf[poz][i];

		if (!viz[vecin]) {
			dfs(vecin);
		}

	}

}

int main() {
	int n, m;
	fin >> n >> m;

	graf.resize(n);
	viz.resize(n);

	int a, b;
	for (int i = 1; i <= m; i++) {
		fin >> a >> b;
		graf[a - 1].push_back(b - 1);
		graf[b - 1].push_back(a - 1);
	}

	int cnt = 0;

	for (int i = 0; i < n; i++) {

		if (!viz[i]) {
			cnt++;
			dfs(i);
		}

	}

	fout << cnt;

	return 0;
}