Cod sursa(job #2287744)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 22 noiembrie 2018 14:04:47
Problema Sortare topologica Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
#include<stdlib.h>
int n,i,j,k,m,c[50001],*g[50001],a[100000],b[100000],w[50001],v[50001],t,o;
void E(int i) {
    c[i]=1;
    for(int j=w[i]-1;j>=0;j--)
    if(!c[g[i][j]])
        E(g[i][j]);
    v[++t]=i;
}
int main() {
    freopen("sortaret.in","r",stdin),freopen("sortaret.out","w",stdout),scanf("%d%d",&n,&m);
    for(k=0;k<m;k++)
        scanf("%d%d",&a[k],&b[k]),w[a[k]]++;
    for(i=1;i<=n;w[i++]=0)
        g[i]=(int*)malloc(w[i]*sizeof(int));
    for(k=0;k<m;k++)
    {
        for(o=i=0;i<w[a[k]]&&!o;i++)
            if(g[a[k]][i]==b[k])
                o=1;
        if(!o)
            g[a[k]][w[a[k]]++]=b[k];
    }
    for(i=1;i<=n;i++)
    if(!c[i])
        E(i);
    for(j=n;j;j--)
        printf("%d ",v[j]);
}