Cod sursa(job #3295228)

Utilizator anamarias12Serbanoiu Ana-Maria anamarias12 Data 3 mai 2025 17:45:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cmath>
#include <cstdio>
#include <vector>

#include <iostream>
#include <algorithm>
using namespace std;

void dfsRec(vector<vector<int>> &adj, vector<bool> &visited, int s) {
	visited[s] = true;
	// vizitez recursiv toate muschiile adiacente
	for (int x : adj[s]) {
		if (visited[x] == false) {
			dfsRec(adj, visited, x);
		}
	}
}

int dfs(vector<vector<int>> &adj) {
	vector<bool> visited(adj.size(), false);
	int cnt = 0;
	for(int i = 1; i < adj.size(); i++) {
		if (!visited[i]) {
			cnt++;
			dfsRec(adj, visited, i);
		}
	}
	return cnt;
}

int main() {
	// determinati numarul componentelor conexe ale grafului neorientat
	// parcurgeri dfs noduri nemarcate si marcarea lor in aceste parcurgeri
	// N nr noduri, M nr muchii
	// lista cu muchiile

	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	int N, M, a, b;

	cin >> N >> M;

	vector<vector<int>> adj(N + 1);

	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int res = dfs(adj);

	cout << res;

	return 0;
}