Cod sursa(job #2694747)

Utilizator S_CatalinStan Catalin-Ionel S_Catalin Data 10 ianuarie 2021 17:53:48
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int NLIM = 100005;

int N, M, nrComponente = 0;
bool vizitat[NLIM];
vector <int> Muchii[NLIM];

void DFS(int Nod) {
	vizitat[Nod] = true;
	for (unsigned int i = 0; i <= Muchii[Nod].size(); i++) {
		int Vecin = Muchii[Nod][i];
		if (!vizitat[Vecin])
			DFS(Vecin);
	}
}

void Citire() {
		fin >> N >> M; // Citim numarul de noduri, respectiv de muchii
		for (int i = 1; i <= M; i++) {
			int x, y;
			fin >> x >> y; // Citim muchiile
			Muchii[x].push_back(y);
			Muchii[y].push_back(x);
		}
		for (int i = 1; i <= N; i++) {
			if (!vizitat[i]) {
				++nrComponente;
				DFS(i);
			}
		}
}

int main() {
	Citire();
	cout << nrComponente;
	return 0;
}