Cod sursa(job #3041893)

Utilizator tudorobretinTudor Obretin tudorobretin Data 2 aprilie 2023 13:18:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

void dfs (vector<vector<int>>& edges, vector<bool>& viz, int& i) {
	for (int j = 0; j < edges[i].size(); j++) {
		int next = edges[i][j];
		if (!viz[next]) {
			viz[next] = true;
			dfs(edges, viz, next);
		}
	}
}

int main() {

	int n, m; fin >> n >> m;

	vector<vector<int>> edges(n);
	vector<bool> viz(n);

	for (int i = 0; i < m; i++) {
		int a, b;	
		fin >> a  >> b; a--; b--;
		
		edges[a].push_back(b);
		edges[b].push_back(a);	
	}
	
	int count = 0;
	for (int i = 0; i < n; i++) {
		if (!viz[i]) {
			viz[i] = true;
			count++;
			dfs(edges, viz, i);
		}
	}
	fout << count;	

	return 0;
}