Pagini recente » Cod sursa (job #1064008) | Cod sursa (job #412472) | Cod sursa (job #460355) | Cod sursa (job #1575173) | Cod sursa (job #795752)
Cod sursa(job #795752)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MAX_N 50000
#define MAX_M 100000
typedef struct edge {
int x;
int y;
struct edge* next;
} edge_t;
typedef enum color {
WHITE,
GRAY,
BLACK
} color_t;
typedef struct node {
edge_t* edges;
color_t col;
} node_t;
void add_edge(node_t* g, int x, int y)
{
edge_t* e = malloc(sizeof(*e));
e->x = x;
e->y = y;
e->next = g[x].edges;
g[x].edges = e;
}
void dfs(node_t* g, int node, void (*f)(int node))
{
node_t* n = &g[node];
edge_t* e;
assert(n->col == WHITE);
n->col = GRAY;
for (e = n->edges; e; e = e->next) {
if (g[e->y].col == WHITE) {
dfs(g, e->y, f);
}
}
n->col = BLACK;
f(node);
}
void init(const char* input, const char* output)
{
freopen(input, "r", stdin);
freopen(output, "w", stdout);
}
node_t graph[MAX_N + 1];
int n;
int g_tsort[MAX_N];
int g_tsort_cnt = 0;
void topo_sort_cb(int node)
{
g_tsort[g_tsort_cnt++] = node;
}
void topo_sort(node_t* g, int n)
{
int i;
for (i = 1; i <= n; i++) {
if (g[i].col == WHITE)
dfs(g, i, topo_sort_cb);
}
}
void read()
{
int i, m;
scanf("%d", &n);
scanf("%d", &m);
for (i = 0; i < m; i++) {
int x, y;
scanf("%d %d", &x, &y);
add_edge(graph, x, y);
}
}
void write()
{
int i;
for (i = g_tsort_cnt - 1; i >= 0; i--) printf("%d ", g_tsort[i]);
}
int main()
{
init("sortaret.in", "sortaret.out");
read();
topo_sort(graph, n);
write();
return 0;
}