Cod sursa(job #1828077)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 12 decembrie 2016 19:26:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
/**
*/
#include <cstdio>
#define maxn 50010

struct nod
        {int v;nod* next;} *lv[maxn],*aux;
//am definit listele a.i. lv[x] = adresa de inceput a listei in care memoram vecinii lui x
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);
        //bag y in lista de vecini a lui x. Cel mai eficient este sa adaugam la inceput
        //adik inainte de primul:
        aux=new nod;
        aux->v=y;
        aux->next=lv[x];
        lv[x]=aux;
        //actualizez shi gradul intern al lui y:
        gr[y]++;
    }
    //Incep coada cu nodurile care au gradul 0:
    pq=1;uq=0;
    for(i=1;i<=n;i++)if(!gr[i])q[++uq]=i;
    //kt timp coada este nevida:
    f=fopen("sortaret.out","w");
    while(pq<=uq)
    {
        //afishez nodul curent:
        fprintf(f,"%d ",q[pq]);
        //procesez nodul pq: tuturor vecinilor sai le scad gradul cu 1
        //daca in timpul acestui proces vreunul capata gradul 0 -> il bag in coada
        for(aux=lv[q[pq]];aux;aux=aux->next)
        {
            gr[aux->v]--;
            if(!gr[aux->v])q[++uq]=aux->v;
        }
        pq++;
    }
    return 0;
}