Pagini recente » Cod sursa (job #369335) | Cod sursa (job #910299) | Cod sursa (job #1342136) | Cod sursa (job #1917634) | Cod sursa (job #2644185)
#include <stdio.h>
#include <vector>
using namespace std;
void dfs(vector<vector<int>> &arcs, vector<int> &inboundArcs,vector<int> &finalOrder, int currentNode) {
if (inboundArcs[currentNode] != 0)
return;
inboundArcs[currentNode] = -1;
finalOrder.push_back(currentNode);
for(int i=0; i<arcs[currentNode].size(); ++i) {
--inboundArcs[arcs[currentNode][i]];
if (inboundArcs[arcs[currentNode][i]] == 0)
dfs(arcs, inboundArcs, finalOrder, arcs[currentNode][i]);
}
arcs[currentNode].clear();
}
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out" , "w", stdout);
int n, m, x, y;
scanf("%d%d", &n, &m);
vector<int> finalOrder;
vector<vector<int>> arcs(n+1);
vector<int> inboundArcs(n+1);
for(int i=0; i<m; ++i) {
scanf("%d%d", &x, &y);
arcs[x].push_back(y);
inboundArcs[y]++;
}
for(int i=1; i<=n; ++i)
if (inboundArcs[i] == 0)
dfs(arcs, inboundArcs, finalOrder, i);
for(int i=0; i<finalOrder.size(); ++i)
printf("%d ", finalOrder[i]);
return 0;
}