Pagini recente » Cod sursa (job #1619004) | Cod sursa (job #995441) | Cod sursa (job #559119) | Cod sursa (job #2407821) | Cod sursa (job #2796139)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <unordered_map>
using namespace std;
class Graph {
//private attributes
vector<vector<int>> edges;
int numberOfNodes;
//-------------------------------------
//private methods
void DFS(unordered_map<int, bool>&, int);
public:
Graph(int);
~Graph();
void setEdge(int, int);
vector<int> distance(int);
int numberOfComponents();
void displayEdges();
};
int main()
{
ifstream in("dfs.in");
ofstream out("dfs.out");
// int numberOfNodes, numberOfEdges, start, from, to;
// in >> numberOfNodes >> numberOfEdges >> start;
int numberOfNodes, numberOfEdges, from, to;
in >> numberOfNodes >> numberOfEdges;
Graph* graph = new Graph(numberOfNodes);
for (int countEdge = 1; countEdge <= numberOfEdges; countEdge++) {
in >> from >> to;
graph->setEdge(from, to);
graph->setEdge(to, from);
}
// graph->displayEdges();
out << graph->numberOfComponents();
// vector<int> distance = graph->distance(start);
// for (int i = 1; i < distance.size(); i++) {
// out << distance[i] << " ";
// }
return 0;
}
void Graph::displayEdges() {
for(int node = 1; node <= this->numberOfNodes; node ++) {
for (auto edge: this->edges[node])
cout << node << " " << edge << endl;
}
}
Graph::Graph(int numberOfNodes) {
this->numberOfNodes = numberOfNodes;
this->edges.resize(numberOfNodes + 1);
}
Graph::~Graph() {}
void Graph::setEdge(int from, int to) {
this->edges[from].push_back(to);
}
vector<int> Graph::distance(int from) {
queue<int> queue;
vector<int> visited(this->numberOfNodes + 1, -1);
visited[from] = 0;
queue.push(from);
while (!queue.empty()) {
int node = queue.front();
for (auto edge : this->edges[node]) {
if (visited[edge] == -1) {
visited[edge] = visited[node] + 1;
queue.push(edge);
}
}
queue.pop();
}
return visited;
}
void Graph::DFS(unordered_map<int, bool> &visited, int start) {
visited[start] = true;
for(int node = 0; node < edges[start].size(); node ++) {
if(!visited[edges[start][node]]) {
DFS (visited ,edges[start][node]);
}
}
}
int Graph::numberOfComponents() {
unordered_map<int ,bool> visited;
int nrOfComp = 0;
for(int node = 1; node <= this->numberOfNodes; node ++) {
if(visited[node] == 0) {
nrOfComp ++;
this->DFS(visited, node);
}
}
return nrOfComp;
}