Cod sursa(job #649455)

Utilizator andunhillMacarescu Sebastian andunhill Data 16 decembrie 2011 08:47:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include<fstream>
#include<vector>
using namespace std;

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

int N, M;

vector<int>graph[50001];
int grad[50001];

class heap
{	int h[65536];
	int pos[50001];
	bool in_h[50001];
	int dim;
	
	public:
		heap()
		{	dim = 0;
		}
		
		void push(int node)
		{	if(in_h[node])
				return;
			
			in_h[node] = 1;
			h[++dim] = node;
			pos[node] = dim;
			up_heap(dim);
		}
		
		void pop()
		{	in_h[h[1]] = 0;
			pos[h[1]] = -1;
			pos[h[dim]] = 1;
			
			swap(h[1], h[dim]);
			dim--;
			down_heap(1);
		}
		
		void up_heap(int p)
		{	while(p > 1 && grad[h[p]] < grad[h[p / 2]])
			{	swap(h[p], h[p / 2]);
				swap(pos[h[p]], pos[h[p / 2]]);
				p /= 2;
			}
		}
		
		void down_heap(int p)
		{	int son;
			do
			{	son = 0;
				if(p * 2 <= dim && grad[h[p]] > grad[h[2 * p]]) son = p * 2;
				if(p * 2 + 1 <= dim && grad[h[p]] > grad[h[2 * p + 1]] && grad[h[2 * p + 1]] < grad[h[2 * p]]) son = 2 * p + 1;
				
				if(son)
				{	swap(h[p], h[son]);
					swap(pos[h[p]], pos[h[son]]);
					p = son;
				}
			}while(son);
		}
		
		void update(int node)
		{	if(pos[node] == -1) return;
			
			up_heap(pos[node]);
			down_heap(pos[node]);
		}
		
		bool empty()
		{	return dim == 0;
		}
		
		int root()
		{	return h[1];
		}
};

heap h;

int main()
{	int i, j, x;
	
	f>>N>>M;
	for(i = 1; i <= M; i++)
	{	f>>j>>x;
		graph[j].push_back(x);
		grad[x]++;
	}
	
	for(i = 1; i <= N; i++) h.push(i);
	while(!h.empty() && grad[h.root()] == 0)
	{	i = h.root(); h.pop();
		g<<i<<" ";
		
		for(j = 0; j < graph[i].size(); j++)
		{	grad[graph[i][j]]--;
			h.update(graph[i][j]);
		}
	}	
	
	f.close();
	g.close();
	return 0;
}