Pagini recente » Cod sursa (job #672745) | Cod sursa (job #1562219) | Cod sursa (job #96137) | Cod sursa (job #1648502) | Cod sursa (job #3199715)
#include <stdio.h>
const int MAX_NODES = 50'000;
const int MAX_EDGES = 100'000;
struct cell {
int v, next;
};
struct node {
int adj;
int in_degree;
};
struct queue {
int a[MAX_NODES];
int head, tail;
void push(int u) {
a[tail++] = u;
}
int pop() {
return a[head++];
}
bool is_empty() {
return head == tail;
}
};
cell list[MAX_EDGES + 1];
node n[MAX_NODES + 1];
queue q;
int num_nodes;
void add_edge(int u, int v) {
static int pos = 0;
list[++pos] = { v, n[u].adj };
n[u].adj = pos;
n[v].in_degree++;
}
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 bfs() {
FILE* f = fopen("sortaret.out", "w");
for (int u = 1; u <= num_nodes; u++) {
if (!n[u].in_degree) {
q.push(u);
}
}
while (!q.is_empty()) {
int u = q.pop();
fprintf(f, "%d ", u);
for (int ptr = n[u].adj; ptr; ptr = list[ptr].next) {
int v = list[ptr].v;
n[v].in_degree--;
if (!n[v].in_degree) {
q.push(v);
}
}
}
fprintf(f, "\n");
fclose(f);
}
int main() {
read_graph();
bfs();
return 0;
}