Cod sursa(job #644332)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 6 decembrie 2011 08:42:17
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>

using namespace std;

FILE *f,*s;

int i,j,k,l,m,n;

int grad[100005],queue[100005];

vector <int> g[100005];

vector <int>:: iterator it;

int main()
{
	f=fopen("sortaret.in","r");
	s=fopen("sortaret.out","w");
	
	fscanf(f,"%d %d",&n,&m);
	
	for(i=1;i<=n;i++)
	{	
		fscanf(f,"%d %d",&j,&k);
		
		g[j].push_back(k);
		
		grad[k]++;
	}
	
	for(i=1;i<=n;i++)
	{
		if(!grad[i]) queue[++queue[0]]=i;
	}	
	
	for(i=1;i<=n;i++)
	{
		l=queue[i];
		
		for(it=g[l].begin();it!=g[l].end();it++)
		{
			grad[*it]--;
			
			if(!grad[*it]) queue[++queue[0]]=*it;
		}	
	}	
	
	for(i=1;i<=queue[0];i++)
		fprintf(s,"%d ",queue[i]);
	
	fclose(s);
	
	return 0;
}