Pagini recente » Cod sursa (job #856390) | Cod sursa (job #877070) | Cod sursa (job #572886) | Cod sursa (job #1608951) | Cod sursa (job #1456570)
#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 edge_mat[n][n], inDeg[n];
// initialize default values
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
edge_mat[i][j] = 0;
}
inDeg[i] = 0;
}
// input data
int x, y;
for (int i = 0; i < m; i++) {
indata >> x >> y;
edge_mat[x-1][y-1] = 1;
inDeg[y-1]++;
}
indata.close();
// TOPOLOGICAL SORT
int nodesWithIndegreeZero[n + 1];
nodesWithIndegreeZero[0] = 0;
// find nodes with no dependency
for (int i = 0; i < n; i++) {
if (inDeg[i] == 0) {
nodesWithIndegreeZero[++(nodesWithIndegreeZero[0])] = i;
}
}
// create the topological order
int topologicalSort[n + 1];
topologicalSort[0] = 0;
while(nodesWithIndegreeZero[0] != 0) {
// add the dependency-free node to the sorted list and remove it from nodes to look at
int node = nodesWithIndegreeZero[nodesWithIndegreeZero[0]--];
topologicalSort[++(topologicalSort[0])] = node;
// remove all dependencies to this node
for (int i = 0; i < n; i++) {
// if dependency exists
if (edge_mat[node][i] == 1) {
// remove dependency
edge_mat[node][i] = 0;
inDeg[i]--;
// if no more dependencies, look at it in the future
if (inDeg[i] == 0) {
nodesWithIndegreeZero[++(nodesWithIndegreeZero[0])] = i;
}
}
}
}
// OUTPUT
ofstream outdata("sortaret.out");
for (int i = 1; i <= n; i++) {
outdata << (topologicalSort[i] + 1) << " ";
}
outdata.close();
return 0;
}