Cod sursa(job #266144)

Utilizator yoyolichIoana Ardeleanu yoyolich Data 24 februarie 2009 22:22:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<stdio.h>
#define maxn 50001
FILE *f=fopen("sortaret.in","r"), *g=fopen("sortaret.out","w");
struct lista{ int x; lista *urm;} *G[maxn],*p;
int n,m,i,x,y,nr;
int viz[maxn],ordine[maxn];

void df(int i)
{
	lista *q;
	for(q=G[i];q;q=q->urm)
		if(!viz[q->x]) df(q->x);
	viz[i]=1;
	ordine[++nr]=i;
}

int main()
{
	fscanf(f,"%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d",&x,&y);
		p=new lista;
		p->x=y;
		p->urm=G[x];
		G[x]=p;
	}
	
	for(i=1;i<=n;i++)
		if(!viz[i]) df(i);
	
	for(i=nr;i>=1;i--) fprintf(g,"%d ",ordine[i]);
	fclose(f);
	fclose(g);
	return 0;
}