Pagini recente » Cod sursa (job #3036733) | Cod sursa (job #1814848) | Cod sursa (job #2105528) | Cod sursa (job #3032131) | Cod sursa (job #3199728)
#include <stdio.h>
const int MAX_NODES = 50'000;
const int MAX_EDGES = 100'000;
struct cell {
int v, next;
};
struct node {
int adj;
bool seen;
};
cell list[MAX_EDGES + 1];
node n[MAX_NODES + 1];
int order[MAX_NODES], order_size;
int num_nodes;
void add_edge(int u, int v) {
static int pos = 0;
list[++pos] = { v, n[u].adj };
n[u].adj = pos;
}
void read_graph() {
FILE* f = fopen("sortaret.in", "r");
int num_edges, u, v;
fscanf(f, "%d %d", &num_nodes, &num_edges);
while (num_edges--) {
fscanf(f, "%d %d", &u, &v);
add_edge(u, v);
}
fclose(f);
}
void dfs(int u) {
if (n[u].seen) {
return;
}
n[u].seen = true;
for (int ptr = n[u].adj; ptr; ptr = list[ptr].next) {
dfs(list[ptr].v);
}
order[order_size++] = u;
}
void dfs_driver() {
for (int u = 1; u <= num_nodes; u++) {
dfs(u);
}
}
void write_order() {
FILE* f = fopen("sortaret.out", "w");
for (int i = num_nodes - 1; i >= 0; i--) {
fprintf(f, "%d ", order[i]);
}
fputc('\n', f);
fclose(f);
}
int main() {
read_graph();
dfs_driver();
write_order();
return 0;
}