Cod sursa(job #2924494)

Utilizator widzAndrei-Daniel Tava widz Data 3 octombrie 2022 19:11:27
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <vector>


//for convenience
using namespace std;

class Graph
{
private:
	int _nodes, _edges;
	vector<vector<int>> _adj_list;

	void dfs(int node,vector<bool>& visited)
	{
		visited[node-1] = true;
		for (const auto other_node : _adj_list[node-1])
			if (!visited[other_node-1])
				dfs(other_node,visited);
	}


public:
	Graph(int nodes, int edges, vector<vector<int>> adj_list) :
	_nodes(nodes),
	_edges(edges),
	_adj_list(std::move(adj_list)){}


	int conexComponents()
	{
		int components = 0;
		vector<bool> visited(_nodes, false);
		for(int node=1; node<=_nodes; ++node)
		{
			if (!visited[node-1])
			{
				dfs(node,visited);
				++components;
			}
		}
		return components;
	};

};


int main()
{
	int nodes, edges;
	ifstream in("dfs.in");
	in >> nodes >> edges;
	vector<vector<int>> adj_list(nodes);
	for(int node=0; node<edges; ++node)
	{
		int n1, n2;
		in >> n1 >> n2;
		adj_list[n1 - 1].push_back(n2);
		adj_list[n2 - 1].push_back(n1);
	}
	in.close();

	Graph g(nodes, edges, adj_list);
	cout << g.conexComponents();

}