Cod sursa(job #481886)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 1 septembrie 2010 21:53:57
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<fstream>
#include<list>
#define NMAX 50005

using namespace std;

list<int> a[NMAX];
int grad[NMAX], i, n, m, x, y, ok;
list<int>:: iterator it;

int main()
{
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	
	f>>n>>m;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y;
		a[x].push_back(y);
		++grad[y];
	}
	
	ok=1;
	while(ok)
	{
		ok=0;
		for(i=1; i<=n; ++i)
			if (grad[i]==0)
			{
				ok=1;
				break;
			}
		if (i<=n)
		{
			g<<i<<" ";
			for(it=a[i].begin(); it!=a[i].end(); ++it) --grad[*it];
			grad[i]=-1;
		}
	}
	g<<"\n";
	f.close();
	g.close();
	return 0;
}