Cod sursa(job #2782958)

Utilizator vali_27Bojici Valentin vali_27 Data 13 octombrie 2021 16:03:21
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

std::vector<std::vector<int> >la;
std::vector<bool> used;

int N, M, comp;

void citire() {
	std::ifstream f("dfs.in");
	f >> N >> M;
	la.resize(N + 1);
	used.resize(N + 1);
	
	for (int i = 0; i <= M; ++i) {
		int x, y;
		f >> x >> y;
		la[x].push_back(y);
		la[y].push_back(x);
	}
}

void dfs(int nod) {
	std::stack<int> stiva;
	stiva.push(nod);

	while (!stiva.empty()){
		int top = stiva.top();
		stiva.pop();
		used[top] = true;

		for (int vecin : la[top])
			if (!used[vecin])
				stiva.push(vecin);
	}
	comp++;
}

void afis() {
	std::ofstream g("dfs.out");
	g << comp;
}

int main()
{
	citire();
	for (int i = 1; i <= N; ++i)
		if (!used[i])
			dfs(i);

	afis();
}