Cod sursa(job #3314590)

Utilizator DalvDalvGhita Vladut DalvDalv Data 10 octombrie 2025 14:25:28
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

bool explored[100000];
vector<int> graf[100001];

void dfs(int nod) {
	for(int vecin : graf[nod]) {
		if(explored[vecin]) continue;
		explored[vecin] = true;
		dfs(vecin);
	}
}

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

	int compConexe = 0;
	int n, m;
	fin >> n >> m;

	for(int i = 0; i < m; i++) {
		int a, b; fin >> a >> b;

		graf[a].push_back(b);
		graf[b].push_back(a);
	}

	for(int i = 0; i < n; i++) {
		if(explored[i]) {
			continue;
		}
		compConexe++;
		dfs(i);
	}

	fout << compConexe << endl;
}