Pagini recente » Cod sursa (job #744833) | Cod sursa (job #1601804) | Cod sursa (job #556651) | Cod sursa (job #1457346) | Cod sursa (job #352670)
Cod sursa(job #352670)
#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;
visited[node] = 1;
for (i = startPos[node]; i < startPos[node] + order[i]; 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;
scanf("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
order[x]++;
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 = 0;
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 (!visited[i]) visit(i);
}
for (i = 1; i <= n; i++) {
printf("%d ", sorted[i]);
}
fclose(stdout);
return 0;
}