Cod sursa(job #559480)

Utilizator zeroblitz36FMI - Roscaneanu George zeroblitz36 Data 17 martie 2011 20:57:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<algorithm>
#include<cstdio>
#include<list>
#include<queue>
using namespace std;
int n,m,k[50001],i,j;
FILE *in,*out;
int main()
{
	in=fopen("sortaret.in","r");
	out=fopen("sortaret.out","w");
	fscanf(in,"%d %d",&n,&m);
	list<int> v[n+1];
	list<int> :: iterator it;
	queue<int> q;
	while(m--)
	{
		fscanf(in,"%d %d",&i,&j);
		v[i].push_back(j);
		k[j]++;
	}
	for(i=1;i<=n;i++) if(!k[i])q.push(i);
	while(!q.empty())
	{
		i=q.front();
		q.pop();
		fprintf(out,"%d ",i);
		for(it=v[i].begin();it!=v[i].end();it++)
		{
			k[*it]--;
			if(!k[*it]) q.push(*it);
		}
	}
	fclose(in);fclose(out);
	return 0;
}