Cod sursa(job #2773198)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 5 septembrie 2021 15:45:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>

const int MAX_N = 100001;
const int MAX_M = 200001;

int n, m;
int components = 0;
bool flag[MAX_M] = { 0 };
std::vector<int> graph[MAX_N];

void read()
{
	std::ifstream input("dfs.in");
	input >> n >> m;
	int x, y;
	for (int count(0); count < m; ++count) {
		input >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	input.close();
}

void print()
{
	std::ofstream output("dfs.out");
	output << components << '\n';
	output.close();
}

void dfs(int vertex)
{
	flag[vertex] = true;
	for (auto neighbor : graph[vertex]) {
		if (!flag[neighbor]) {
			dfs(neighbor);
		}
	}
}

void connected_components()
{
	for (int vertex(1); vertex <= n; ++vertex) {
		if (!flag[vertex]) {
			++components;
			dfs(vertex);
		}
	}
}

int main()
{
	read();
	connected_components();
	print();
	return 0;
}