Cod sursa(job #2649587)

Utilizator StefanSanStanescu Stefan StefanSan Data 15 septembrie 2020 12:23:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include      <iostream>
#include      <fstream>
#include      <algorithm>
#include      <vector>

using namespace std;

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

vector < int > graf[100001];
bool vizitat[100001];

void dfs(int nod) {
	for (int i = 0; i < graf[nod].size(); i++) {
		if (!vizitat[graf[nod][i]]) {
			vizitat[graf[nod][i]] = true;
			dfs(graf[nod][i]);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);
	
	int n, m, a, b, nr = 0;
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> a >> b;
		graf[a].push_back(b);
		graf[b].push_back(a);
	}

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

	out << nr;

	return 0;
	 
}