Cod sursa(job #2668242)

Utilizator BulaceanuAlexandraBulaceanu Alexandra-Irina BulaceanuAlexandra Data 4 noiembrie 2020 18:00:08
Problema Parcurgere DFS - componente conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector<int> muchii[100010];
map<int, bool> vizitat;

void dfs(int nodCurent) {
	vizitat[nodCurent] = true;
	for (int vecin : muchii[nodCurent]) {
		if (!vizitat[vecin]) {
			dfs(vecin);
		}
	}
}

int main() {
	int nrCompConexe = 0;
	int n, m, x, y;
	fin >> n >> m;

	for (int i = 1; i <=m; i++) {
		fin >> x >> y;
		muchii[x].push_back(y);
		muchii[y].push_back(x);
	}

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

	fout << nrCompConexe;
}