Pagini recente » Cod sursa (job #1336059) | Cod sursa (job #277809) | Cod sursa (job #1386563) | Cod sursa (job #1782789) | Cod sursa (job #1456599)
#include <fstream>
#include <iostream>
#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[]) {
bool isVisited = true;
for (vector<int>::iterator vit = (*unvisited).begin(); vit < (*unvisited).end(); vit++) {
if (*vit == node) {
isVisited = false;
(*unvisited).erase(vit);
break;
}
}
if (!isVisited) {
for(vector<int>::iterator vit = edges[node].begin(); vit < edges[node].end(); vit++) {
visit(*vit, topologicalSort, unvisited, edges);
}
(*topologicalSort).insert((*topologicalSort).begin(), 1, node);
}
}