Pagini recente » Cod sursa (job #1582639) | Cod sursa (job #1733498) | Cod sursa (job #1191171) | Cod sursa (job #2091941) | Cod sursa (job #2780433)
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
class Graph
{
private:
int nodes_count;
int edges_count;
unordered_map<int, vector<int>> edges;
void addEdge(int a, int b)
{
edges[a].push_back(b);
edges[b].push_back(a);
}
queue<int> _dfs(int node, vector<bool> &visited)
{
queue<int> result;
stack<int> stack;
stack.push(node);
while (!stack.empty())
{
int topNode = stack.top();
stack.pop();
if (!visited[topNode])
{
result.push(topNode);
visited[topNode] = true;
}
for (int adjacentEdge : edges[topNode])
{
if (!visited[adjacentEdge])
stack.push(adjacentEdge);
}
}
return result;
}
public:
int connectedComponents()
{
int connectedComponentsCount = 0;
vector<bool> visited(nodes_count + 1, false);
for (int node = 1; node < nodes_count + 1; node++)
if (!visited[node])
{
_dfs(node, visited);
connectedComponentsCount++;
}
return connectedComponentsCount;
}
queue<int> dfs(int node)
{
vector<bool> visited(nodes_count + 1, false);
return _dfs(node, visited);
}
void readFromFile(string filePath)
{
ifstream input = ifstream(filePath);
input >> nodes_count;
input >> edges_count;
for (int i = 0; i < edges_count; i++)
{
int a, b;
input >> a >> b;
addEdge(a, b);
}
}
};
int main()
{
ofstream output("dfs.out");
Graph g = Graph();
g.readFromFile("dfs.in");
output << g.connectedComponents();
return 0;
}