Pagini recente » Cod sursa (job #2196174) | Cod sursa (job #2491587) | Cod sursa (job #1944684) | Cod sursa (job #2750033) | Cod sursa (job #1114754)
#include <iostream>
#include <queue>
#include <fstream>
#include <stack>
using namespace std;
class TopSort {
private:
stack<int> q;
vector< pair<int, int> > edges;
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;
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));
}
}
vector<int> adjacent(int vertex) {
vector<int> result;
vector< pair<int, int> >::iterator it;
for (it = edges.begin(); it != edges.end(); it++) {
if (it->first == vertex) {
result.push_back(it->second);
}
}
return result;
}
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;
vector<int> adj = adjacent(start_vertex);
for (int i = 0; i < adj.size(); i++) {
top_sort(adj[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;
}