Pagini recente » Cod sursa (job #1775334) | Cod sursa (job #3256329) | Cod sursa (job #1176607) | Cod sursa (job #1061930) | Cod sursa (job #2784595)
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
class Graph
{
private:
int numberOfNodes, numberOfEdges;
vector<vector<int>> listOfNeighbours;
public:
Graph(int numberOfNodes = 0, int numberOfEdges = 0)
{
this->numberOfNodes = numberOfNodes;
this->numberOfEdges = numberOfEdges;
}
~Graph()
{
this->numberOfEdges = 0;
this->numberOfNodes = 0;
}
void setNumberOfEdges(int);
void setNumberOfNodes(int);
void setEdges(int, int);
int getNumberOfNodes();
int getNumberOfEdges();
void readEdges(istream &in);
void printlistOfNeighbours(ostream &out);
int numberOfConnectedComponents(bool[]);
private:
void DFS(int node, bool[]);
};
void Graph::setNumberOfEdges(int m)
{
numberOfEdges = m;
}
void Graph::setNumberOfNodes(int n)
{
numberOfNodes = n;
}
void Graph::setEdges(int firstNode, int secondNode)
{
listOfNeighbours[firstNode].push_back(secondNode);
}
int Graph::getNumberOfNodes()
{
return numberOfNodes;
}
int Graph::getNumberOfEdges()
{
return numberOfEdges;
}
void Graph::readEdges(istream &in)
{
int firstNode, secondNode;
listOfNeighbours.resize(numberOfNodes + 2);
for (int i = 0; i < this->numberOfEdges; i++)
{
in >> firstNode >> secondNode;
setEdges(firstNode, secondNode);
setEdges(secondNode, firstNode);
}
}
void Graph::printlistOfNeighbours(ostream &out)
{
for (int i = 1; i < this->listOfNeighbours.size() - 1; i++)
{
out << i << ": ";
for (int j = 0; j < listOfNeighbours[i].size(); j++)
out << this->listOfNeighbours[i][j] << " ";
}
}
void Graph::DFS(int node, bool visited[])
{
// int visited[listOfNeighbours.size()];
visited[node] = 1;
//out<<node<<" ";
for (int neighbour : listOfNeighbours[node])
{
// out<<neighbour<<" ";
if (!visited[neighbour])
DFS(neighbour, visited);
}
}
int Graph::numberOfConnectedComponents(bool visited[])
{
int numberOfConnectedComponents = 0;
for (int i = 1; i <= numberOfNodes; i++)
{
if (visited[i] == 0)
{
numberOfConnectedComponents++;
DFS(i, visited);
}
}
return numberOfConnectedComponents;
}
int main()
{
int numberOfNodes, numberOfEdges;
in >> numberOfNodes >> numberOfEdges;
Graph Gr(numberOfNodes, numberOfEdges);
Gr.readEdges(in);
bool visited[numberOfNodes];
out << Gr.numberOfConnectedComponents(visited);
return 0;
}