Pagini recente » Cod sursa (job #2356708) | Cod sursa (job #1696020) | Cod sursa (job #2272865) | Cod sursa (job #1106956) | Cod sursa (job #2918134)
#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 current_vertice, stack<int>& stack, vector<bool>& visited_vertices)
{
visited_vertices[current_vertice] = true;
for (int i = 0; i < graph[current_vertice].size(); i++)
{
if (!visited_vertices[graph[current_vertice][i]])
{
topological_sort(graph, graph[current_vertice][i], stack, visited_vertices);
}
}
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);
for (int i = 1; i <= no_of_vertices; i++)
{
if (!visited_vertices[i])
{
topological_sort(graph, i, stack, visited_vertices);
}
}
print_stack(stack);
return 0;
}