Cod sursa(job #2800842)

Utilizator AsandeiStefanAsandei Stefan-Alexandru AsandeiStefan Data 14 noiembrie 2021 09:31:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>

enum NodeState {
	NOT_VISITED, VISITED
};

struct Node {
	std::vector<int> neighbours;
	NodeState state = NOT_VISITED;
};

Node graph[100001];
int count, m, n, a, b;
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");

void dfs(int nodeIndex) {

	graph[nodeIndex].state = VISITED;

	for (auto& subNodeIndex : graph[nodeIndex].neighbours) {
		if (graph[subNodeIndex].state == NOT_VISITED) {
			dfs(subNodeIndex);
		}
	}
}

int main() {
	fin >> n >> m;
	
	for (int i = 0; i < m; i++) {
		fin >> a >> b;

		graph[a].neighbours.push_back(b);
		graph[b].neighbours.push_back(a);
	}

	for (int i = 1; i <= n; i++) {
		if (graph[i].state == NOT_VISITED) {
			count++;
			dfs(i);
		}
	}
	fout << count;
	return 0;
}