Cod sursa(job #315224)

Utilizator stanesealexStanese Alex stanesealex Data 14 mai 2009 20:19:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<cstdio>

using namespace std;

struct graf
{
	int a;
	graf *next;
};
graf *x[100010],*ult[100010];
int c[100010],viz[100010],grad[100010];
int main()
{
	int n,m,i,u,y,j;
	graf *p;
	FILE *f=fopen("sortaret.in","r");
	FILE *g=fopen("sortaret.out","w");
	fscanf(f,"%d %d ",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d ",&u,&y);
		if (x[u]==NULL)
		{
			p=new graf;
			p->next=NULL;
			p->a=y;
			ult[u]=p;
			x[u]=p;
			grad[y]++;
		}
		else
		{
			p=new graf;
			p->a=y;
			ult[u]->next=p;
			p->next=NULL;
			ult[u]=p;
			grad[y]++;
		}
	}
	j=0;
	while (j<n)
	{
		for (i=1;i<=n;i++)
			if (grad[i]==0&&viz[i]==0)
			{
				j++;
				c[j]=i;
				viz[i]=1;
				p=new graf;
				p=x[i];
				while (p)
				{
					grad[p->a]--;
					p=p->next;
				}
			}
	}
	for (i=1;i<=n;i++)
		fprintf(g,"%d ",c[i]);
	fclose(f);
	fclose(g);
	return 0;

}