Cod sursa(job #1465343)

Utilizator RengelBotocan Bogdan Rengel Data 27 iulie 2015 00:52:19
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 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);

		for each (uint32 neighbor in neighbors[x])
		{
			extRank[neighbor] -= 1;
		
			if (extRank[neighbor] == 0)
			{
				queue.push(neighbor);
			}
		}
	}

	return 0;
}


// --- functions
// ...