Cod sursa(job #522285)

Utilizator invatacelTudorache Marius invatacel Data 14 ianuarie 2011 18:26:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;

int h_index[1<<16];
int in[1<<16];

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);

	vector<pair<int,int> > V;
	int n,m;
	scanf ("%d%d",&n,&m);

	for (int i=0;i<m;i++)
	{
		int a,b;
		scanf ("%d%d",&a,&b);
		V.push_back(make_pair(a,b));
		in[b]++;
	}

	sort(V.begin(),V.end());
	
	for (int i=0;i<m;i++)
		if (V[i].first != V[0].first && h_index[V[i].first] == 0)
			h_index[V[i].first] = i;

	queue<int> q;
	for (int i=1;i<=n;i++)	
		if (in[i] == 0)
			q.push(i);

	while (q.size() > 0)
	{
		int t = q.front();
		q.pop();
		printf ("%d ",t);
		for (int h = h_index[t];h < V.size() && V[h].first == t ;h++)
		{
			if (V[h].first != t) break;			
			
			if (--in[V[h].second] == 0) q.push(V[h].second);
		}
	}

	printf ("\n");
	return 0;
}