Cod sursa(job #152184)

Utilizator mariaciPopa Marius Ionut mariaci Data 9 martie 2008 10:21:17
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
int n,m,viz[100];
typedef struct nod
{ int x;
  nod *next;
}*pNod;
pNod l[100],a;
void add(int x,int y)
{ pNod p=new nod;
  p->x=y;
  p->next=l[x];
  l[x]=p;
}
void citire()
{ freopen("sortaret.in","r",stdin);
  freopen("sortaret.out","w",stdout);
  scanf("%d%d",&n,&m);
  int i,x,y;
  for(i=1;i<=m;i++)
     { scanf("%d%d",&x,&y);
       add(x,y);
     }
  fclose(stdin);
}

void push(int x)
{ pNod p=new nod;
  p->x=x;
  p->next=a;
  a=p;
}

void df(int nod)
{ viz[nod]=1;
  for(pNod q=l[nod];q;q=q->next)
      if(viz[q->x]==0) df(q->x);
  viz[nod]=2;
  push(nod);
}
void sortare()
{ int i;
  for(i=1;i<=n;i++)
     if(viz[i]==0) df(i);
}
int main()
{ citire();
  sortare();
  pNod q;
  for(q=a;q;q=q->next)
      printf("%d ",q->x);
  printf("\n");
  return 0;
}