Cod sursa(job #182943)

Utilizator hadesgamesTache Alexandru hadesgames Data 21 aprilie 2008 15:32:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
typedef struct nod
{
	int x;
	nod *a;
	
} *pnod;
	FILE *in,*out;
pnod a[50000],varf;
int coada[50000];
int viz[50000];
int viz2[50000];
void add(int x,int y)
{
	pnod p=new nod;
	p->a=a[x];
	p->x=y;;
	a[x]=p;
	
}
void dfs(int x)
{
	pnod p;
//	fprintf(out,"%d\n",x);
	viz2[x]=1;
	for (p=a[x];p;p=p->a)
	{
		if (viz2[p->x]==0)
			dfs(p->x);
	}
	viz2[x]=2;
	p=new nod;
	p->x=x;
	p->a=varf;
	varf=p;
}
int main()
{
	int u=0,u2,s,x,y,n,m,i;

	pnod p;
	in=fopen("sortaret.in","r");
	out=fopen("sortaret.out","w");
	fscanf(in,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(in,"%d%d",&x,&y);
		add(x,y);
	}
/*	for (i=1;i<=n;i++)
	{
		fprintf(out,"%d: ",i);
		for (p=a[i];p;p=p->a)
			fprintf(out,"%d ",p->x);
		fprintf(out,"\n");
	}*/
	for (i=1;i<=n;i++)
		if (viz2[i]==0)
		{
			dfs(i);
		}
/*	while (u!=n)
	{
		u2=u;
		for (i=s;i<=u2;i++)
		{
			p=a[coada[i]];
			while (p)
			{
				if (!viz2[p->x])
				{
					u++;
					coada[u]=p->x;
					viz2[p->x]=1;
				}
				p=p->a;
			}
		}
		s=u2+1;
	}*/
	
	for (p=varf;p;p=p->a)
		fprintf(out,"%d ",p->x);
	fprintf(out,"\n");
	fclose(in);
	fclose(out);
	return 0;
}