Pagini recente » Cod sursa (job #1823630) | Cod sursa (job #858616) | Cod sursa (job #1804362) | Cod sursa (job #1062071) | Cod sursa (job #2791948)
#include <bits/stdc++.h>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
class Graph
{
private:
int numberOfNodes, numberOfEdges;
vector<vector<int>> listOfNeighbours;
bool isDirected;
public:
Graph(int numberOfNodes = 0, int numberOfEdges = 0, bool isDirected = 0)
{
this->numberOfNodes = numberOfNodes;
this->numberOfEdges = numberOfEdges;
this->isDirected = isDirected;
}
~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[]);
void BFS(int, bool[], int[]);
void topologicalSorting(bool[], stack<int>&);
private:
void DFS(int, bool[]);
void topologicalSortingDFS(int, bool[], stack<int>&);
};
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);
if (!isDirected)
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<<endl;
if (!visited[neighbour])
DFS(neighbour, visited);
}
}
int Graph::numberOfConnectedComponents(bool visited[])
{
int numberOfConnectedComponents = 0;
for (int i = 1; i <= this->numberOfNodes; i++)
{
if (!visited[i])
{
// out << numberOfNodes << endl;
numberOfConnectedComponents++;
DFS(i, visited);
}
}
return numberOfConnectedComponents;
}
void Graph::BFS(int sourceNode, bool visited[], int distance[])
{
queue<int> queueBFS;
queueBFS.push(sourceNode);
visited[sourceNode] = 1;
distance[numberOfNodes] = {0};
while (!queueBFS.empty())
{
for (int node : listOfNeighbours[queueBFS.front()])
{
if (!visited[node])
{
visited[node] = 1;
queueBFS.push(node);
distance[node] = distance[queueBFS.front()] + 1;
}
}
queueBFS.pop();
}
for (int node = 1; node <= numberOfNodes; node++)
{
if (sourceNode != node && distance[node] == 0)
out << "-1 ";
else
out << distance[node] << " ";
}
}
void Graph::topologicalSortingDFS(int node, bool visited[], stack<int> &stack)
{
visited[node] = 1;
for (int neighbour : listOfNeighbours[node])
{
if (!visited[neighbour])
topologicalSortingDFS(neighbour, visited, stack);
}
stack.push(node);
}
void Graph::topologicalSorting(bool visited[], stack<int> &stack)
{
for (int i = 1; i <= this->numberOfNodes; i++)
{
if (!visited[i])
topologicalSortingDFS(i, visited, stack);
}
while (!stack.empty())
{
out << stack.top() << " ";
stack.pop();
}
}
int main()
{
int numberOfNodes, numberOfEdges, sourceNode;
in >> numberOfNodes >> numberOfEdges;
Graph Gr(numberOfNodes, numberOfEdges, 1);
Gr.readEdges(in);
bool visited[numberOfNodes + 1] = {0};
int distance[numberOfNodes + 1] = {0};
stack<int> stack;
// out << Gr.numberOfConnectedComponents(visited);
// Gr.printListOfNeighbours(out);
//Gr.BFS(sourceNode, visited, distance);
Gr.topologicalSorting(visited, stack);
return 0;
}