Cod sursa(job #649461)

Utilizator andunhillMacarescu Sebastian andunhill Data 16 decembrie 2011 09:26:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
//Using a heap

#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int N, M;

vector<int>graph[50001];
queue<int>q;
int grad[50001];
typedef vector<int>::iterator it;

int main()
{	int i, x, y;
	
	f>>N>>M;
	for(i = 1; i <= M; i++)
	{	f>>x>>y;
		graph[x].push_back(y);
		grad[y]++;
	}
	
	for(i = 1; i <= N; i++) 
		if(!grad[i]) q.push(i);
	
	while(!q.empty())
	{	i = q.front(); q.pop();
		
		g<<i<<" ";
		for(it k = graph[i].begin(); k != graph[i].end(); k++)
		{	grad[*k]--;
			if(!grad[*k])
				q.push(*k);
		}
	}
	f.close();
	g.close();
	return 0;
}