Cod sursa(job #153065)

Utilizator rethosPaicu Alexandru rethos Data 10 martie 2008 08:44:16
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>
#define NM 500001
struct lista{int inf;lista *urm;} *G[NM];
int n,m,viz[NM],v[NM],k;
int nod_neviz()
{ int i;
  for (i=1;i<=n;i++) if (viz[i]==0) return i;
  return 0;
}
void intr(int x,int y)
{ if (G[x]==NULL)
	{ G[x]->inf=y;
	  G[x]->urm=NULL;
	}
  else
	{ lista *p=new lista;
	  p->inf=y;
	  p->urm=G[x];
	  G[x]=p;
	}
}
void df(int x)
{ lista *p;
  for (p=G[x];p->urm!=NULL;p=p->urm)
	if (viz[p->inf]==0)
		{ viz[p->inf]=1;
		  v[++k]=p->inf;
		  df(p->inf);
		}
}
int main()
{ freopen("sortaret.in","rt",stdin);
  freopen("sortaret.out","wt",stdout);
  scanf("%d %d",&n,&m);
  int i,x,y;
  for (i=1;i<=m;i++)
	{ scanf("%d %d",&x,&y);
	  intr(x,y);
	}
  x=nod_neviz();
  while(x)
	{ viz[x]=1;
	  v[++k]=x;
	  df(x);
	  x=nod_neviz();
	}
  for (i=1;i<=n;i++) printf("%d ",v[i]);
  fclose(stdin);
  fclose(stdout);
  return 0;
}