Cod sursa(job #2340381)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 10 februarie 2019 13:05:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 1e5;
const int MAXM = 2e5;

int n, m, cnt;
vector<int> g[MAXN + 1];
bool viz[MAXN + 1];

void dfs(int nod) {
	viz[nod] = 1;
	for (auto x : g[nod]) {
		if (!viz[x])
			dfs(x);
	}
}

int main() {
	in >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		int x, y;
		in >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	for (int i = 1; i <= n; ++ i) {
		if (!viz[i]) {
			dfs(i);
			++ cnt;
		}
	}

	out << cnt;

	return 0;
}