Pagini recente » Cod sursa (job #1664933) | Cod sursa (job #1650535) | Cod sursa (job #2258380) | Cod sursa (job #1463236) | Cod sursa (job #1456581)
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{
// INPUT
ifstream indata("sortaret.in");
int n, m;
indata >> n >> m;
int inDeg[n] = {0};
vector<int> edges[n];
// input data
int x, y;
for (int i = 0; i < m; i++) {
indata >> x >> y;
// set edges and inDegree of nodes
edges[x - 1].push_back(y - 1);
inDeg[y - 1]++;
}
indata.close();
// TOPOLOGICAL SORT
int topologicalSort[n + 1] = {0};
// first add all nodes which don't have dependencies
for (int i = 0; i < n; i++) {
if (inDeg[i] == 0) {
topologicalSort[++topologicalSort[0]] = i;
}
}
// now browse through nodes and remove dependencies
for (int i = 1; i <= n; i++) {
int dependencyFreeNode = topologicalSort[i];
// remove all edges going out from this node and update inDegrees accordingly
for(vector<int>::iterator vit = edges[dependencyFreeNode].begin(); vit < edges[dependencyFreeNode].end(); vit++) {
inDeg[*vit]--;
if (inDeg[*vit] == 0) {
topologicalSort[++topologicalSort[0]] = *vit;
}
}
}
// OUTPUT
ofstream outdata("sortaret.out");
for (int i = 1; i <= n; i++) {
outdata << (topologicalSort[i] + 1) << " ";
}
outdata.close();
return 0;
}