Cod sursa(job #559186)

Utilizator zeroblitz36FMI - Roscaneanu George zeroblitz36 Data 17 martie 2011 17:48:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<cstdio>
#include<algorithm>
#include<list>
using namespace std;
FILE *in,*out;
int n,m,i,j,k[50001];
int main()
{
	in=fopen("sortaret.in","r");
	fscanf(in,"%d %d",&n,&m);
    list<int> v[n+1],w[n+1],s;
	for(;m;m--)
	{
		fscanf(in,"%d %d",&i,&j);
		v[i].push_back(j);
		w[j].push_back(i);
	}
	for(i=1;i<=n;i++)
	{
		if(w[i].empty()) {s.push_back(i);}
	}
	out=fopen("sortaret.out","w");
	while(!s.empty())
	{
		i=s.front();
		s.pop_front();
		fprintf(out,"%d ",i);
		while(!v[i].empty())
		{
			if(k[v[i].front()]==0)
			{
				k[v[i].front()]=1;
				s.push_back(v[i].front());
			}
				v[i].pop_front();
		}
	}
}