Pagini recente » Cod sursa (job #120070) | Cod sursa (job #1057747) | Cod sursa (job #2815208) | Cod sursa (job #2796325) | Cod sursa (job #1538308)
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 50000
typedef struct node{
int data;
struct node * next;
} node;
node *G[MAX_NODES];
int inDegree[MAX_NODES];
int queue[MAX_NODES], q_curr, q_tail;
void push(int n) {
queue[q_tail++] = n;
}
int pop() {
return queue[q_curr++];
}
void add(int from, int to) {
node * p = malloc(sizeof(node));
p->data = to;
p->next = G[from];
G[from] = p;
}
void readGraph(int m, FILE * in) {
int i, from, to;
for (i = 1; i <= m; i++) {
fscanf(in, "%d %d", &from, &to);
add(from - 1, to - 1);
inDegree[to - 1]++;
}
}
void printTopoSort(int n, FILE *out) {
int i, curr_node;
node * adj;
for (i = 0; i < n; i++) {
if (!inDegree[i]) {
push(i);
}
}
while (q_curr < q_tail) {
curr_node = pop();
fprintf(out, "%d ", curr_node + 1);
for (adj = G[curr_node]; adj; adj = adj->next) {
--inDegree[adj->data];
if (!inDegree[adj->data]) {
push(adj->data);
}
}
}
}
int main() {
FILE * in, * out;
int m, n;
in = fopen("sortaret.in", "r");
fscanf(in, "%d %d", &n, &m);
readGraph(m, in);
fclose(in);
out = fopen("sortaret.out", "w");
printTopoSort(n, out);
fclose(out);
return 0;
}