Pagini recente » Cod sursa (job #1777492) | Cod sursa (job #1000764) | Cod sursa (job #1463229) | Cod sursa (job #2303523) | Cod sursa (job #1456615)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void visit(int, vector<int>&, vector<int>&, vector<int>[]);
int main(int argc, char **argv)
{
// INPUT
ifstream indata("sortaret.in");
int n, m;
indata >> n >> m;
vector<int> edges[n];
vector<int> unvisited;
// input data
int x, y;
for (int i = 0; i < m; i++) {
indata >> x >> y;
// set edges
edges[x - 1].push_back(y - 1);
}
for (int i = 0; i < n; i++) {
// set unvisited nodes
unvisited.push_back(i);
}
indata.close();
// TOPOLOGICAL SORT
vector<int> topologicalSort;
while(unvisited.size() != 0) {
int last = unvisited.back();
visit(last, topologicalSort, unvisited, edges);
}
// OUTPUT
ofstream outdata("sortaret.out");
for (int i = 0; i < n; i++) {
outdata << (topologicalSort[i] + 1) << " ";
}
outdata.close();
return 0;
}
void visit(int node, vector<int>& topologicalSort, vector<int>& unvisited, vector<int> edges[]) {
vector<int>::iterator unvit = find(unvisited.begin(), unvisited.end(), node);
if (unvit != unvisited.end()) {
unvisited.erase(unvit);
for(vector<int>::iterator vit = edges[node].begin(); vit < edges[node].end(); vit++) {
visit(*vit, topologicalSort, unvisited, edges);
}
topologicalSort.insert(topologicalSort.begin(), 1, node);
}
}