Pagini recente » Cod sursa (job #2824072) | Cod sursa (job #1471075) | Cod sursa (job #2472207) | Cod sursa (job #1538258) | Cod sursa (job #2788242)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
//#include "Graph.h"
//#include "DirectedGraph.h"
//#include "UndirectedGraph.h"
using namespace std;
class Graph {
int nrNodes; //number of nodes
vector<vector<int>> edges; // list of connections between nodes
public:
Graph(int _nrNodes);
int getNrNodes() const;
void setEdge(int node, int neighbour);
int nrConnectedComponents();
void printEdges();
~Graph();
private:
void DFS(int, vector<int>&);
};
Graph::Graph(int _nrNodes)
{
this -> nrNodes = _nrNodes;
this -> edges.resize(this -> nrNodes + 1, vector<int>());
/*
* Nodes start from 1, but index starts at 0
*/
}
int Graph::getNrNodes() const
{
return this -> nrNodes;
}
int Graph::nrConnectedComponents()
{
int ans = 0;
vector<int>visited(this -> nrNodes+1, 0);
for(int i = 1 ; i <= this -> nrNodes; ++i)
if(visited[i] == 0)
{
DFS(i, visited);
++ans;
}
return ans;
}
void Graph::DFS(int start, vector<int>& visited)
{
visited[start] = 1;
for(int i = 0; i < edges[start].size(); ++i)
{
int neighbour = edges[start][i];
if(visited[neighbour] == 0)
{
visited[neighbour] = 1;
DFS(neighbour, visited);
}
}
}
Graph::~Graph()
{
this -> nrNodes = 0;
for(int i = 1; i <= edges.size(); ++i)
this -> edges[i].clear();
}
void Graph::printEdges()
{
for(int i = 1; i < edges.size(); i++)
{
cout << i<< ": ";
for(auto it: edges[i])
cout << it<< " ";
cout << "\n";
}
}
void Graph::setEdge(int node, int neighbour)
{
this ->edges[node].push_back(neighbour);
}
//------------------------------------------------------------------------------------------
class UndirectedGraph: public Graph{
public:
UndirectedGraph(int _nrNodes);
void addEdge(int node, int neighbour);
~UndirectedGraph();
};
UndirectedGraph::UndirectedGraph(int _nrNodes): Graph(_nrNodes){}
void UndirectedGraph::addEdge(int node, int neighbour)
{
this -> setEdge(node, neighbour);
this -> setEdge(neighbour, node);
}
UndirectedGraph::~UndirectedGraph() {}
int main()
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, x, y;
fin >> n >> m;
UndirectedGraph *ug = new UndirectedGraph(n);
for(int i = 1; i <= m; i++)
{
fin >> x >> y;
ug -> addEdge(x, y);
}
fout << ug -> nrConnectedComponents();
return 0;
}