Cod sursa(job #3352582)

Utilizator rapidu36Victor Manz rapidu36 Data 29 aprilie 2026 09:01:38
Problema Sortare topologica Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>

#define N 50000
#define M 100000
#define NIL (-1)

struct element {
    int varf, urm;
};

typedef struct element element;

element v[M];
int lst[N+1], nr_pred[N+1], nr_v, q[N];

void adauga(int x, int y) {
    // il adaugam pe y in lista de succesori a lui x
    v[nr_v].varf = y;
    v[nr_v].urm = lst[x];
    lst[x] = nr_v++;
    nr_pred[y]++;
}

int main() {
    FILE *in, *out;
    in = fopen("sortaret.in", "r");
    out = fopen("sortaret.out", "w");
    int m, n;
    fscanf(in, "%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        lst[i] = NIL;
        nr_pred[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        fscanf(in, "%d%d", &x, &y);
        adauga(x, y);
    }
    fclose(in);
    int st = 0, dr = st - 1;
    for (int i = 1; i <= n; i++) {
        if (nr_pred[i] == 0) {
            q[++dr] = i;
        }
    }
    while (st <= dr) {
        int x = q[st++];
        fprintf(out, "%d ", x);
        for (int p = lst[x]; p != NIL; p = v[p].urm) {
            int y = v[p].varf;
            nr_pred[y]--;
            if (nr_pred[y] == 0) {
                q[++dr] = y;
            }
        }
    }
    fprintf(out, "\n");
    fclose(out);
    return 0;
}