Cod sursa(job #1262956)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 13 noiembrie 2014 19:09:10
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#define MAXN 50000
#define MAXM 100000
int q[MAXN], lista[MAXN+1], nrp[MAXN+1], val[MAXM+1], next[MAXM+1];
int main(){
    int n, m, x, y, i, st, dr, p;
    FILE *fin, *fout;
    fin=fopen("sortaret.in", "r");
    fout=fopen("sortaret.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d", &x, &y);
        val[i]=y;
        next[i]=lista[x];
        lista[x]=i;
        nrp[y]++;
    }
    st=0;
    dr=0;
    for(i=1; i<=n; i++){
        if(nrp[i]==0){
            q[dr++]=i;
        }
    }
    while(st<dr){
        fprintf(fout, "%d ", q[st]);
        p=lista[q[st++]];
        while(p!=0){
            nrp[val[p]]--;
            if(nrp[val[p]]==0){
                q[dr++]=val[p];
            }
            p=next[p];
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}