Cod sursa(job #2377546)

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

using namespace std;

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

class Nod {
private:
	int id;
	Nod *nxt;
public:
	Nod() {
		id = 0;
		nxt = NULL;
	}
	Nod(int v) {
		id = v;
		nxt = NULL;
	}
	int getId() {
		return id;
	}
	Nod *getNxt() {
		return nxt;
	}
	void modifyNxt(Nod *nod) {
		nxt = nod;
	}
};

void push(Nod **x, int val) {
	if (x == NULL) {
		*x = new Nod(val);
		return;
	}
	Nod *aux = new Nod(val);
	aux -> modifyNxt(*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 -> getNxt())
		if (!viz[son -> getId()])
			dfs(son -> getId());
}

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;
}