Cod sursa(job #1465345)

Utilizator creativedoughnutCreative Doughnut creativedoughnut Data 27 iulie 2015 00:55:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

// --- basics
#define int16 short
#define int32 int
#define int64 int long long
#define uint16 unsigned int16
#define	uint32 unsigned int32
#define uint64 unsigned int64

// --- prototypes
// ...

/// --- input/output files
#define INPUT_FILE	"sortaret.in"
#define	OUTPUT_FILE	"sortaret.out"

int main()
{
	freopen(INPUT_FILE, "r", stdin);
	freopen(OUTPUT_FILE, "w", stdout);

	uint32 N, M;
	scanf("%u %u", &N, &M);

	vector<vector<uint32>> neighbors;
	neighbors.resize(N);

	vector<uint32> extRank;
	extRank.resize(N);

	for (uint32 i = 0; i < M; i++)
	{
		uint32 x, y;
		scanf("%u %u", &x, &y);

		neighbors[x - 1].push_back(y - 1);
		extRank[y - 1] += 1;
	}

	queue<uint32> queue;
	for (uint32 i = 0; i < N; i++)
	{
		if (extRank[i] == 0)
		{
			queue.push(i);
		}
	}

	while (!queue.empty())
	{
		uint32 x = queue.front();
		queue.pop();

		printf("%u ", x + 1);

		uint32 size = neighbors[x].size();
		for (uint32 i = 0; i < size; i++)
		{
			uint32 neighbor = neighbors[x][i];

			extRank[neighbor] -= 1;

			if (extRank[neighbor] == 0)
			{
				queue.push(neighbor);
			}
		}
	}

	return 0;
}


// --- functions
// ...