Cod sursa(job #504446)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 27 noiembrie 2010 18:38:35
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
#include<stdlib.h>
#define NR 50001
typedef struct
{long st[NR],sp;}stiva;
stiva s;

typedef struct Nod
{long info;
struct Nod *next;}nod,*list;
list l[NR];

long n,i,j,k,m,c[NR],t=0;

void init(stiva &s)
{s.sp=0;}

int empty(stiva s)
{return s.sp==0;}

void push(stiva &s,long x)
{s.st[++s.sp]=x;}

long pop(stiva &s)
{return s.st[s.sp--];}
         
int apartine(list l,long x)
{list c;
for(c=l;c!=NULL;c=c->next)
if(c->info==x)
        return 1;
return 0;}

void add(list &l,long x)
{nod *p,*nou=new nod;
nou->info=x;
nou->next=NULL;
if(l==NULL)
       {l=nou;
       return;}
p=l;
while(p->next!=NULL)
       p=p->next;
p->next=nou;}         

void explorare(stiva &s,long i)
{long j;
c[i]=1;
for(j=n;j>=1;j--)
if(c[j]==0&&apartine(l[i],j)==1)
        explorare(s,j);
push(s,i);}

int main()
{freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%ld %ld",&n,&m);
for(k=1;k<=m;k++)
       {scanf("%ld %ld",&i,&j);
       add(l[i],j);}
for(i=1;i<=n;i++)
       c[i]=0;
for(i=1;i<=n;i++)
if(c[i]==0)
       explorare(s,i);
while(!empty(s))
       printf("%ld ",pop(s));
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;}