Cod sursa(job #2424554)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 23 mai 2019 11:24:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#define maxn 50010

struct nod
{
    int v;
    nod* next;
} *lv[maxn],*aux;

int gr[maxn],q[maxn];

int main()
{
    FILE *f=fopen("sortaret.in","r");
    int n,m,i,x,y,pq,uq;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        aux=new nod;
        aux->v=y;
        aux->next=lv[x];
        lv[x]=aux;
        gr[y]++;
    }
    pq=1;uq=0;
    for(i=1;i<=n;i++)if(!gr[i])q[++uq]=i;
    f=fopen("sortaret.out","w");
    while(pq<=uq)
    {
        fprintf(f,"%d ",q[pq]);

        for(aux=lv[q[pq]];aux;aux=aux->next)
        {
            gr[aux->v]--;
            if(!gr[aux->v])q[++uq]=aux->v;
        }
        pq++;
    }
    return 0;
}