Cod sursa(job #395620)

Utilizator GotenAmza Catalin Goten Data 13 februarie 2010 16:09:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<stdio.h>
int q,ver[100100],leg[100100],start[50100],c[50100],in[50100];
int main()
{
	int n,m,x,y,p,t,i;
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	while(m--)
	{
		scanf("%d %d",&x,&y);
		ver[++q]=y;
		leg[q]=start[x];
		start[x]=q;
		in[y]++;
	}
	for(i=1;i<=n;i++)
		if(!in[i])
			c[++c[0]]=i;
	p=1;	
	while(c[0]<n)
	{
		t=start[c[p]];
		while(t)
		{
			in[ver[t]]--;
			if(!in[ver[t]])
				c[++c[0]]=ver[t];
			t=leg[t];
		}
		p++;
	}
	for(i=1;i<=n;i++)
		printf("%d ",c[i]);
	return 0;
}