Cod sursa(job #992883)

Utilizator diac_paulPaul Diac diac_paul Data 2 septembrie 2013 18:15:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define NMax 50001

int n, m, d[NMax], q[NMax], in, sf;
vector<int> v[NMax];

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

	scanf("%d %d", &n, &m);

	while (m--)
	{
		int x, y;
		scanf("%d %d", &x, &y);

		v[x].push_back(y);
		d[y]++;
	}

	sf = -1;
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
			q[++sf] = i;
	}

	while (in <= sf)
	{		
		for (int j = 0; j < v[q[in]].size(); j++)
		{
			d[v[q[in]][j]]--;
			if (d[v[q[in]][j]] == 0)
			{
				q[++sf] = v[q[in]][j];
			}
		}
		in++;
	}

	for (int i = 0; i < n; i++)
		printf("%d ", q[i]);
	printf("\n");

	return 0;
}