Pagini recente » Cod sursa (job #2545222) | tema | Istoria paginii runda/oji201756 | Cod sursa (job #759684) | Cod sursa (job #1456551)
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{
// input data
ifstream indata("sortaret.in");
int n, m;
indata >> n >> m;
int edge_mat[n][n];
int inDeg[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
edge_mat[i][j] = 0;
}
inDeg[i] = 0;
}
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 of nodes
vector<int> nodesWithNoIncomingEdges;
for (int i = 0; i < n; i++) {
if (inDeg[i] == 0) {
nodesWithNoIncomingEdges.push_back(i);
}
}
vector<int> topologicalSort;
while(nodesWithNoIncomingEdges.size() != 0) {
int last = nodesWithNoIncomingEdges.back();
nodesWithNoIncomingEdges.pop_back();
topologicalSort.push_back(last);
for (int i = 0; i < n; i++) {
// if a node has a dependency on this one
// remove it (remove the edge)
if(edge_mat[last][i] == 1) {
edge_mat[last][i] = 0;
inDeg[i]--;
// if that was the only dependency,
// add node to topSort
if (inDeg[i] == 0) {
nodesWithNoIncomingEdges.push_back(i);
}
}
}
}
// output data
ofstream outdata("sortaret.out");
for (size_t i = 0; i < topologicalSort.size(); i++) {
outdata << (topologicalSort[i] + 1) << " ";
}
outdata.close();
return 0;
}