Cod sursa(job #1808941)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 18 noiembrie 2016 13:55:13
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#define MAXN 50001
#define MAXM 100001
int val[MAXM],next[MAXM],k,c[MAXN-1];
struct numar
{
    int pred,succ;
}v[MAXN];
inline void add(int i,int j)
{
    v[j].pred++;
    val[++k]=j;
    next[k]=v[i].succ;
    v[i].succ=k;
}
inline void update(int i)
{
    v[i].pred=-1;
    int p=v[i].succ;
    while(p)
    {
        v[val[p]].pred--;
        p=next[p];
    }
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("sortaret.in","r");
    fout=fopen("sortaret.out","w");
    int n,m,i,x,y;
    fscanf(fin,"%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        add(x,y);
    }
    char ok=1;
    while(ok)
    {
        ok=m=0;
        for(i=1;i<=n;i++)
            if(!v[i].pred)
            {
                ok=1;
                c[m++]=i;
            }
        for(i=0;i<m;i++)
        {
            update(c[i]);
            fprintf(fout,"%d ",c[i]);
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}