Pagini recente » Cod sursa (job #2627499) | Cod sursa (job #2559826) | Cod sursa (job #34326) | Cod sursa (job #826484) | Cod sursa (job #2924496)
#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);
ofstream out("dfs.out");
out << g.conexComponents();
out.close();
}