Cod sursa(job #1980957)

Utilizator dezenStefan Brasoveanu dezen Data 14 mai 2017 14:08:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>
using namespace std;
int n,m,x,y,i,g[50002],j,v[50002],u,primu;
struct nod
{
    int info;
    nod *urm;
}*prim[50002];
void adaug(int x,int y)
{
    nod *p;
    p=new nod;
    p->info=x;
    p->urm=prim[y];
    prim[y]=p;
}
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        adaug(y,x);
        g[y]++;
    }
    for(i=1;i<=n;i++)
    {
        if(g[i]==0)
        {
            printf("%d ",i);
            v[u]=i;
            u++;
        }
    }
    while(primu<=u)
    {
        nod *p;
        for(p=prim[v[primu]] ; p ; p=p->urm)
        {
            g[p->info]--;
            if(g[p->info]==0)
            {
                v[u]=p->info;
                u++;
                printf("%d ",p->info);
            }
        }
        primu++;
    }
    return 0;
}