Pagini recente » Cod sursa (job #669738) | Cod sursa (job #351119) | Cod sursa (job #2535901) | Cod sursa (job #1076345) | Cod sursa (job #2792978)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
//Graph class, all the nodes start from 0
class Graph
{
private:
//number of nodes
int n;
//number of edges
int e;
//bool if graph is oriented
bool oriented;
//adj list for graph representation
vector<vector<int>> adj_list;
public:
Graph(int n, bool oriented)
{
this->n = n;
this->e = 0;
this->oriented = oriented;
//populate adj list with empty vectors
vector<int> empty;
for (int i = 0; i < n; i++)
{
this->adj_list.push_back(empty);
}
}
virtual ~Graph() {}
void add_edge(int node1, int node2)
{
this->e++;
this->adj_list[node1].push_back(node2);
//if graph is not oriented, then push from the second node
if (!this->oriented)
{
this->adj_list[node2].push_back(node1);
}
}
void top_sort_dfs(int current_node, vector<bool> &visited, stack<int> &stck)
{
visited[current_node] = true;
for (int i = this->adj_list[current_node].size() - 1; i >= 0; i--)
{
int neighbour;
neighbour = adj_list[current_node][i];
if (!visited[neighbour])
{
top_sort_dfs(neighbour, visited, stck);
}
}
stck.push(current_node);
}
void topological_sort()
{
vector<bool> visited(this->n, false);
stack<int> stck;
for (int i = 0; i < this->n; i++)
{
if (!visited[i])
{
top_sort_dfs(i, visited, stck);
}
}
while (!stck.empty())
{
fout << stck.top() + 1 << " ";
stck.pop();
}
}
};
int main()
{
//number of nodes
int N;
//number of edges
int E;
fin >> N >> E;
Graph graph(N, true);
int n1, n2;
for (int i = 0; i < E; i++)
{
fin >> n1 >> n2;
graph.add_edge(n1 - 1, n2 - 1);
}
graph.topological_sort();
return 0;
}