Cod sursa(job #2819884)

Utilizator george_buzasGeorge Buzas george_buzas Data 19 decembrie 2021 12:46:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

bitset<100001> is_visited;
vector<int> neighbors[100001]; // if there is value y on position x => there is a vertice between x and y

void dfs(int node) {
	is_visited[node] = true;
	int length = neighbors[node].size();
	for (int i = 0; i < length; ++i) {
		if (!is_visited[neighbors[node][i]]) {
			dfs(neighbors[node][i]);
		}
	}
}

int main() {
	int nr_nodes, nr_vertices;
	fin >> nr_nodes >> nr_vertices;
	int node_1, node_2;
	for (int vertex = 1; vertex <= nr_vertices; ++vertex) {
		fin >> node_1 >> node_2;
		neighbors[node_1].push_back(node_2);
		neighbors[node_2].push_back(node_1);
	}
	int cnt_connected_components = 0;
	for (int node = 1; node <= nr_nodes; ++node) {
		if (!is_visited[node]) {
			++cnt_connected_components;
			dfs(node);
		}
	}
	fout << cnt_connected_components;
	return 0;
}