Cod sursa(job #2809633)

Utilizator teofilotopeniTeofil teofilotopeni Data 27 noiembrie 2021 11:53:57
Problema Parcurgere DFS - componente conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;

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

void findConexComponents(int i) {
	finded[i] = 1;
	for (; nodes[i].size(); nodes[i].pop()) {
		if (!finded[nodes[i].top()]) {
			findConexComponents(nodes[i].top());
		}
	}
}

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