Cod sursa(job #674625)

Utilizator AplayLazar Laurentiu Aplay Data 6 februarie 2012 16:17:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct nod{ int x;
                     nod *urm ; }NODE;
NODE *v[50001];
int n,m,grad[50001], c[50001];

void citire()
{
    FILE *f=fopen("sortaret.in","r");
    fscanf(f,"%d%d",&n,&m);
    NODE *p;
    int x,y;
    for(int i=0;i<m;++i)
    {
        fscanf(f,"%d%d",&x,&y);
        p=(NODE*)malloc(sizeof(NODE));
        p->x=y;
        p->urm = v[x];
        v[x]=p;
        grad[y]++;
    }
}

void sortare()
{
    FILE*f=fopen("sortaret.out","w");
    int p=0,u=0;
    NODE *q;
    for(int i=1;i<=n;++i)
        if(!grad[i]) c[u++]=i;
    --u;
    while(p<=u)
    {
        fprintf(f,"%d ",c[p]);
        q=v[c[p]];
        while(q)
        {
            grad[q->x]--;
            if(grad[q->x]==0) c[++u]=q->x;
            q=q->urm;
        }
        ++p;
    }
    fclose(f);
}

int main()
{
    citire();
    sortare();
    return 0;
}