Pagini recente » Cod sursa (job #587957) | Cod sursa (job #151199) | Cod sursa (job #2357235) | Cod sursa (job #2778046) | Cod sursa (job #2918054)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
std::ifstream fin("sortaret.in");
std::ofstream fout("sortaret.out");
void topological_sort(vector<vector<int>> graph, int no_of_vertices, int current_vertice, stack<int>& stack, vector<bool>& visited_vertices)
{
if (!visited_vertices[current_vertice])
{
visited_vertices[current_vertice] = true;
if (graph[current_vertice].size() > 0)
{
int i = 0;
while (i < graph[current_vertice].size())
{
topological_sort(graph, no_of_vertices, graph[current_vertice][i], stack, visited_vertices);
i++;
}
}
stack.push(current_vertice);
}
}
void print_stack(stack<int> stack)
{
while (!stack.empty()) {
fout << ' ' << stack.top();
stack.pop();
}
}
void add_edges(vector<vector<int>>& graph, int no_of_edges)
{
int from_vertex{ 0 };
int to_vertex{ 0 };
for (int i = 1; i <= no_of_edges; i++)
{
fin >> from_vertex >> to_vertex;
graph[from_vertex].push_back(to_vertex);
}
}
int main() {
int no_of_vertices{ 0 };
int no_of_edges{ 0 };
fin >> no_of_vertices;
fin >> no_of_edges;
vector<vector<int>> graph(no_of_vertices + 1);
add_edges(graph, no_of_edges);
stack<int> stack;
vector<bool> visited_vertices(no_of_vertices + 1);
topological_sort(graph, no_of_vertices, 1, stack, visited_vertices);
print_stack(stack);
return 0;
}