Cod sursa(job #1090275)

Utilizator RRomaniucRomaniuc Radu Andrei RRomaniuc Data 22 ianuarie 2014 15:38:21
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<stdio.h>
using namespace std;
struct nod{int info; nod *urm;};
nod *prim[50100], *p, *q; int grad[50100]; bool viz[50100];
void update(int i)
{
    viz[i]=1;
    for(p=prim[i];p!=NULL;p=p->urm){   //nu inteleg de nu merge sa pun p->urm!=NULL, chiar daca pierd solutii.
        delete q; grad[p->info]--; q=p;
    }
    printf("%d ",i);
}
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    int n,i,x,y,nr;
    scanf("%d%d",&n,&nr); for(i=1;i<=nr;i++){
        scanf("%d%d",&x,&y); grad[y]++;
        //x este inaintea lui y.
        p=new nod;
        p->info=y;
        p->urm=prim[x];
        prim[x]=p;
        }

    //verificare liste.
    /*for(p=prim[1];p!=NULL;p=p->urm)
        printf("%d ",p->info);*/
    //perfect in regula!

    for(i=1;i<=n;i++)if(grad[i]==0&&viz[i]==0){
        update(i);i=1;
    }

    for(i=1;i<=n;i++)if(viz[i]==0)printf("%d ",i);

    return 0;
}