Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #855143) | Cod sursa (job #853025) | Cod sursa (job #1456601)
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
void visit(int, vector<int>*, map<int, bool>*, vector<int>[]);
int main(int argc, char **argv)
{
// INPUT
ifstream indata("sortaret.in");
int n, m;
indata >> n >> m;
vector<int> edges[n];
map<int, bool> 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[i] = true;
}
indata.close();
// TOPOLOGICAL SORT
vector<int> topologicalSort;
for (int i = 0; i < n; i++) {
int last = unvisited.at(i);
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, map<int, bool>* unvisited, vector<int> edges[]) {
if ((*unvisited)[node] == true) {
(*unvisited)[node] = false;
for(vector<int>::iterator vit = edges[node].begin(); vit < edges[node].end(); vit++) {
visit(*vit, topologicalSort, unvisited, edges);
}
(*topologicalSort).insert((*topologicalSort).begin(), 1, node);
}
}