Cod sursa(job #2627768)

Utilizator bogdanf555Fuia Bogdan bogdanf555 Data 12 iunie 2020 14:18:13
Problema Sortare topologica Scor 60
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <stdio.h>
#include <stdlib.h>

#define mare 50003

typedef struct {

    int a[mare];
    int size;
} Queue;

typedef struct {
    int edge[mare];
    int size;
} List;

int dequeue(Queue *q) {

    int elem;

    if(q -> size != 0)
        elem = q -> a[0];
    else
        elem = 0;

    for(int i = 0; i < q -> size; i++) {

        q -> a[i] = q -> a[i + 1];
    }
    q -> size--;

    return elem;
}

void enqueue(Queue *q, int elem) {

    q -> a[q -> size] = elem;
    q -> size++;
}

int ind[mare];
List *list;

int main()
{
    int n, m;

    FILE *fin, *fout;
    fin = fopen("sortaret.in", "r");
    fout = fopen("sortaret.out", "w");

    if(!fin || !fout)
        printf("nope");

    fscanf(fin, "%d %d", &n, &m);

    Queue q;
    q.size = 0;

    list = (List *) calloc(n + 3, sizeof(List));

    for(int i = 0; i < m; i++) {

        int x, y;
        fscanf(fin, "%d %d", &x, &y);
        ind[y]++;
        list[x].edge[list[x].size++] = y;
    }

    for(int i = 1; i <= n; i++) {
        if(ind[i] == 0) {
            enqueue(&q, i);
            ind[i] = -1;
        }
    }

    while(q.size != 0) {

        int node = dequeue(&q);

        fprintf(fout, "%d ", node);

        for(int j = 0; j < list[node].size; j++) {
            ind[list[node].edge[j]]--;
        }

        for(int x = 1; x <= n; x++) {
            if(ind[x] == 0) {
                enqueue(&q, x);
                ind[x] = -1;
            }
        }
    }
    fclose(fin);
    fclose(fout);

    return 0;
}