Cod sursa(job #2377541)

Utilizator flibiaVisanu Cristian flibia Data 10 martie 2019 15:49:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Nod {
	int id;
	Nod *nxt;
	Nod(int v) {
		id = v;
		nxt = NULL;
	}
};

void push(Nod **x, int val) {
	if (x == NULL) {
		*x = new Nod(val);
		return;
	}
	Nod *aux = new Nod(val);
	aux -> nxt = *x;
	*x = aux;
}

int n, m, cnt, x, y, viz[100100];
Nod *v[100100];

void dfs(int nod) {
	viz[nod] = 1;
	for (auto son = v[nod]; son != NULL; son = son -> nxt)
		if (!viz[son -> id])
			dfs(son -> id);
}

int main() {
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> x >> y;
		push(&v[x], y);
		push(&v[y], x);
	}
	for (int i = 1; i <= n; i++)
		if (!viz[i]) {
			cnt++;
			dfs(i);
		}
	out << cnt;
	return 0;
}