Pagini recente » Cod sursa (job #1883275) | Borderou de evaluare (job #2830565) | Cod sursa (job #2242473) | Cod sursa (job #2470326) | Cod sursa (job #352678)
Cod sursa(job #352678)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MAXN 50001
#define MAXM 100001
typedef struct edge {
int xnode;
int ynode;
} Edge;
// Be lazy and have global variables
Edge edge[MAXM];
int startPos[MAXN];
int sorted[MAXN];
int visited[MAXN];
int order[MAXN];
int currentPos = 0;
int edgeCompare(Edge *x, Edge *y) {
if (x->xnode > y->xnode) return 1;
if (x->xnode < y->xnode) return -1;
return 0;
}
// BFS
void visit(int node) {
int i;
assert(!visited[node]);
visited[node] = 1;
for (i = startPos[node]; i < startPos[node] + order[node]; i++) {
assert(edge[i].xnode = node);
if (!visited[edge[i].ynode]) {
visit(edge[i].ynode);
}
}
currentPos++;
sorted[currentPos] = node;
}
int main()
{
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int n, m;
int i, x, y;
int arcsIn[MAXN];
for (i = 1; i <= n; i++) {
arcsIn[i] = 0;
}
scanf("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
order[x]++;
arcsIn[y] = 1;
edge[i].xnode = x;
edge[i].ynode = y;
}
edge[0].xnode = 0;
edge[0].ynode = 0;
qsort(edge, m + 1, sizeof(Edge), edgeCompare);
int orderSum = 1;
for (i = 1; i <= n; i++) {
startPos[i] = orderSum;
orderSum += order[i];
visited[i] = 0;
}
// Do BFS on all nodes
for (i = 1; i <= n; i++) {
if (!arcsIn[i]) {
visit(i);
}
}
for (i = n; i >= 1; i--) {
printf("%d ", sorted[i]);
}
fclose(stdout);
return 0;
}