Cod sursa(job #2809661)

Utilizator teofilotopeniTeofil teofilotopeni Data 27 noiembrie 2021 12:37:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
using namespace std;

bitset<100001> finded;
vector<vector<int>> nodes;

void findConexComponents(int i) {
	if (!finded[i]) {
		finded[i] = 1;
		for (int j = 0; j < nodes[i].size(); j++) {
			findConexComponents(nodes[i][j]);
		}
	}
}

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	int nr, arches, conexComponents = 0;
	scanf("%d %d", &nr, &arches);
	nodes = vector<vector<int>>(nr + 1, vector<int>());
	while (arches-- > 0) {
		int from, to;
		scanf("%d %d", &from, &to);
		nodes[from].push_back(to);
		nodes[to].push_back(from);
	}
	for (int i = 1; i <= nr; i++) {
		conexComponents += !finded[i];
		findConexComponents(i);
	}
	cout << conexComponents;
	return 0;
}