Cod sursa(job #481896)

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

using namespace std;

list<int> a[NMAX];
int grad[NMAX], i, n, m, x, y, ok, c[NMAX], p, u;
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];
	}
	
	for (i=1; i<=n; i++)
		if (grad[i]==0) 
		{
			++u;
			c[u]=i;
			grad[i]=-1;
		}
	p=1;
	while (p<=u)
	{
		g<<c[p]<<" ";
		x=c[p];
		for (it=a[x].begin(); it!=a[x].end(); ++it)
		{
			--grad[*it];
			if (grad[*it]==0)
			{
				++u;
				c[u]=*it;
				grad[*it]=-1;
			}
		}
		++p;
	}
	g<<"\n";
	f.close();
	g.close();
	return 0;
}