Pagini recente » Cod sursa (job #625097) | Cod sursa (job #852159) | Cod sursa (job #2703575) | Cod sursa (job #817882) | Cod sursa (job #1115754)
#include <iostream>
#include <queue>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
class TopSort {
private:
stack<int> q;
vector< pair<int, int> > edges;
vector< vector<int> > adj_list;
int no_vertices, no_edges, *visited;
ifstream in;
ofstream out;
public:
TopSort() {
in.open("sortaret.in");
out.open("sortaret.out");
}
~TopSort() {
in.close();
out.close();
if (NULL != visited) {
delete[] visited;
}
}
void read_graph() {
in >> no_vertices >> no_edges;
adj_list.resize(no_vertices + 1);
visited = new int[no_vertices + 1];
for (int i = 1; i <= no_vertices; i++)
visited[i] = 0;
int left, right;
for (int i = 0; i < no_edges; i++) {
in >> left >> right;
edges.push_back(pair<int, int>(left, right));
adj_list[left].push_back(right);
}
}
int find_unvisited() {
for (int i = 1; i <= no_vertices; i++) {
if (visited[i] == 0) {
return i;
}
}
return -1;
}
void top_sort(int start_vertex) {
if (visited[start_vertex] == 0) {
visited[start_vertex] = 1;
for (unsigned int i = 0; i < adj_list[start_vertex].size(); i++) {
top_sort(adj_list[start_vertex][i]);
}
q.push(start_vertex);
}
}
void solve() {
int vertex;
while ((vertex = find_unvisited()) != -1) {
top_sort(vertex);
}
while (!q.empty()) {
out << q.top() << " ";
q.pop();
}
}
};
int main() {
TopSort prob;
prob.read_graph();
prob.solve();
return 0;
}