Cod sursa(job #519725)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 6 ianuarie 2011 13:06:13
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<stdio.h>
#include<stdlib.h>
#define N 50001
typedef struct nod
{long info;
struct nod *leg;}Nod,*list_ad;
typedef struct
{long grin,grex;
list_ad lad;}head;
typedef head graf[N];

long pop(list_ad &l)
{Nod *c=l->leg;
long x=l->info;
free(l);
l=c;
return x;}

int contine(list_ad &l,long x)
{Nod *c;
for(c=l;c!=NULL;c=c->leg)
if(c->info==x)
      return 1;
return 0;}

void add(list_ad &l,long x)
{Nod *c=new Nod,*p;
c->info=x;
c->leg=NULL;
if(l==NULL)
     {l=c;
     return;}
p=l;
while(p->leg!=NULL)
     p=p->leg;
p->leg=c;}

int main()
{long n,m,k,i,j;
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%ld%ld",&n,&m);
graf g;
list_ad q,s=NULL;
for(i=1;i<=n;i++)
       {g[i].grin=0;
       g[i].grex=0;
       g[i].lad=NULL;}
for(k=1;k<=m;k++)
       {scanf("%ld%ld",&i,&j);
       if(contine(g[i].lad,j)==0)
               {g[j].grin++;
               g[i].grex++;
               add(g[i].lad,j);}}
for(i=1;i<=n;i++)
if(g[i].grin==0)
       add(s,i);
while(s!=NULL)
       {j=pop(s);
       if(g[j].grin==0)
              printf("%ld\n",j);
       for(q=g[j].lad;q!=NULL;q=q->leg)
              {if(g[q->info].grin>0)
                      g[q->info].grin--;
              if(g[j].grex>0)
                      g[j].grex--;
              if(g[q->info].grex==0)
                      printf("%ld\n",q->info);
              else
                      add(s,q->info);}}
fclose(stdin);
fclose(stdout);
return 0;}