Cod sursa(job #3317164)

Utilizator a_violetaAvram Violeta-Iulia a_violeta Data 22 octombrie 2025 16:36:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
//parcurgeri grafuri

//dfs infoarena

//dfs(nod):
//	vizitat[nod]=1;
//	for x in lista_vecini[nod]:
//		if vizitat[x]==0
//			dfs(x);

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");



void dfs(int nod, vector<int>& vizitat, vector<vector<int>>& lista_adiacenta) {
	vizitat[nod] = 1;
	for(int vecin : lista_adiacenta[nod])
		if (vizitat[vecin]==0)
			dfs(vecin, vizitat, lista_adiacenta);
}

int main() {
	int n, m, x, y, nr=0;

	fin >> n >> m;

	vector<vector<int>> lista_adiacenta(n+1);
	vector<int> vizitat(n+1, 0);


	for (int i = 0; i < m; i++) {
		fin >> x >> y;

		lista_adiacenta[x].push_back(y);
		lista_adiacenta[y].push_back(x);

	}

	for (int i = 1; i <= n; i++) {
		if (vizitat[i] == 0) {
			nr++;
			dfs(i, vizitat, lista_adiacenta);
		}
	}

	fout << nr;
	//cout << nr << "\n";

	return 0;
}