Cod sursa(job #2791261)

Utilizator schizofrenieShallan Davar schizofrenie Data 30 octombrie 2021 11:58:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>
#include <vector>

#define MAXN 100000

std::vector<int> muchii[MAXN];

bool viz[MAXN];

void dfs (int nod) {
	viz[nod] = 1;
	for (int to : muchii[nod])
		if (!viz[to])
			dfs(to);
}


int main () {
	int n, m;
	int i;
	int ret;

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

	scanf("%d%d", &n, &m);
	for (i = 0; i != m; ++ i) {
		int de, la;
		scanf("%d%d", &de, &la);
		-- de, -- la;
		muchii[de].emplace_back(la);
		muchii[la].emplace_back(de);
	}

	ret = 0;
	for (i = 0; i != n; ++ i) {
		if (!viz[i]) {
			++ ret;
			dfs(i);
		}
	}

	printf("%d\n", ret);
	return 0;
}