Pagini recente » Cod sursa (job #2822333) | Cod sursa (job #826330) | Cod sursa (job #1761076) | Statistici cont de incercari (Tudor_Gheorghe) | Cod sursa (job #1456584)
#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];
vector<int> edges[n];
for (int i = 0; i < n; i++) {
inDeg[i] = 0;
}
// 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];
topologicalSort[0] = 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;
}