Pagini recente » Cod sursa (job #2569900) | Cod sursa (job #2415508) | Cod sursa (job #877049) | Cod sursa (job #2656554) | Cod sursa (job #1456543)
#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];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
edge_mat[i][j] = 0;
}
}
int x, y;
for (int i = 0; i < m; i++) {
indata >> x >> y;
edge_mat[x-1][y-1] = 1;
}
indata.close();
// topological sort of nodes
vector<int> topologicalSort;
vector<int> nodesWithNoIncomingEdges;
for (int i = 0; i < n; i++) {
bool hasIncoming = false;
for (int j = 0; j < n; j++) {
if (edge_mat[j][i] == 1) {
hasIncoming = true;
break;
}
}
if (hasIncoming == false) {
nodesWithNoIncomingEdges.push_back(i + 1);
}
}
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-1][i] == 1) {
edge_mat[last-1][i] = 0;
// if that was the only dependency,
// add node to topSort
int sum = 0;
for (int j = 0; j < n; j++) {
sum += edge_mat[j][i];
}
if (sum == 0) {
nodesWithNoIncomingEdges.push_back(i + 1);
}
}
}
}
// output data
ofstream outdata("sortaret.out");
for (int i = 0; i < topologicalSort.size(); i++) {
outdata << tologicalSort[i] << " ";
}
outdata.close();
return 0;
}