Cod sursa(job #153056)

Utilizator rethosPaicu Alexandru rethos Data 10 martie 2008 08:31:42
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#define NM 50001
int n,m,viz[NM],v[NM],k;
int a[NM][NM];
int nod_neviz()
{ int i;
  for (i=1;i<=n;i++) if (viz[i]==0) return i;
  return 0;
}
void df(int x)
{ int i;
  for (i=1;i<=a[x][0];i++)
	if (viz[a[x][i]]==0)
		{ viz[a[x][i]]=1;
		  v[++k]=a[x][i];
		  df(i);
		}
}
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);
	  a[x][++a[x][0]]=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;
}