Cod sursa(job #2818521)

Utilizator rapidu36Victor Manz rapidu36 Data 16 decembrie 2021 12:31:55
Problema Sortare topologica Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 50000
#define M 100000

typedef struct
{
    int vf, urm;
} element;

int lst[N+1], nr, n, m, q[N+1], nrp[N+1], s[N+1];
element v[2*M+1];

void adauga(int x, int y)
{//adauga pe y in lista succesorilor a lui x
    v[++nr].vf = y;
    v[nr].urm = lst[x];
    lst[x] = nr;
    nrp[y]++;//x este predecesor al lui y
}

void push(int *pdr, int val)
{
    q[++(*pdr)] = val;
}

void pop(int *pst)
{
    ++(*pst);
}

int front(int st)
{
    return q[st];
}

bool empty(int st, int dr)
{
    return (st > dr);
}

void bfs()
{
    int st_q = 0, dr_q = -1;
    ///initializarea vectorului d
    for (int i = 1; i <= n; i++)
    {
        if (nrp[i] == 0)
        {
            push(&dr_q, i);
        }
    }
    n = 0;
    while (!empty(st_q, dr_q))
    {
        int x = front(st_q);
        pop(&st_q);
        s[++n] = x;
        for (int p = lst[x]; p != 0; p = v[p].urm)
        {
            int y = v[p].vf;
            nrp[y]--;
            if (nrp[y] == 0)
            {
                push(&dr_q, y);
            }
        }
    }
}

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);
    }
    bfs();
    for (int i = 1; i <= n; i++)
    {
        fprintf(out, "%d ", s[i]);
    }
    fclose(in);
    fclose(out);
    return 0;
}