Cod sursa(job #1107519)

Utilizator AndreiBarbutaAndrei Barbuta AndreiBarbuta Data 13 februarie 2014 22:27:25
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>

using namespace std;
int pred[50001];
int succ [50000][50000];
int q[50001];
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int i,m,n,u=0,p=1,x,y,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        succ[x][0]++;
        succ[x][succ[x][0]]=y;
        pred[y]++;
    }
    p=1;
    for(i=1;i<=n;++i)
        if(pred[i]==0)
            q[++u]=i;
    while(p<=u)
    {
        for(i=1;i<=succ[q[p]][0];++i)
        {
            if(pred[succ[q[p]][i]]>0)
            {
               pred[succ[q[p]][i]]--;
               if(pred[succ[q[p]][i]]==0)
                    q[++u]=succ[q[p]][i];
            }
        }
        p++;
    }
    for(i=1;i<=u;++i)
        printf("%d ",q[i]);
    return 0;
}