Cod sursa(job #3221835)

Utilizator rapidu36Victor Manz rapidu36 Data 8 aprilie 2024 10:52:45
Problema Sortare topologica Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>
#define N 50000
#define M 100000

typedef struct
{
    int vf, urm;
} element;

element v[M+1];
int n, m, nv, lst[N+1], nrp[N+1], q[N+1];

void adauga(int x, int y)
{
    ///il adauga pe y in lista succesorilor lui x
    nv++;
    v[nv].vf = y;
    v[nv].urm = lst[x];
    lst[x] = nv;
}

int main()
{
    FILE *in, *out;
    in = fopen("sortaret.in", "r");
    out = fopen("sortaret.out", "w");
    fscanf(in, "%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        fscanf(in, "%d%d", &x, &y);
        adauga(x, y);
        nrp[y]++;
    }
    int st = 0, dr = -1;
    for (int i = 1; i <= n; i++)
    {
        if (nrp[i] == 0)///adaugam initial in coada varfurile fara predecesori
        {
            q[++dr] = i;
        }
    }
    while (st <= dr)///cat timp q nu e vida
    {
        int x = q[st++];///il scoatem pe x din coada q
        fprintf(out, "%d ", x);
        for (int p = lst[x]; p != 0; p = v[p].urm)///parcurgem lista succesorilor lui x
        {
            int y = v[p].vf;
            nrp[y]--;
            if (nrp[y] == 0)
            {
                q[++dr] = y;///il adaugam pe y in coada
            }
        }
    }
    fclose(in);
    fclose(out);
    return 0;
}