Pagini recente » Monitorul de evaluare | Diferente pentru problema/heist intre reviziile 76 si 46 | Atasamentele paginii Profil Elena_Strugari | Diferente pentru problema/heist intre reviziile 76 si 28 | Cod sursa (job #1457678)
#include <fstream>
#include <vector>
using namespace std;
///// DESCRIPTION
// THIS PROGRAM PERFORMS A TOPOLOGICAL SORT
// OF THE VERTICES OF A DIRECTED ACYCLIC GRAPH
// BY STEP-WISE ELIMINATION OF "DEPENDENCIES"
/////
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];
// 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;
}