Cod sursa(job #331791)

Utilizator SliMMStefan Saftescu SliMM Data 15 iulie 2009 12:54:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
/*
 * sortare_topologică.cpp
 *
 *  Created on: Jul 14, 2009
 *      Author: stefan
 */

#include <cstdio>
#include <cstring>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

	long int N, M;
	long int a, b, i, *grad;
	vector<long int>* vecini;
	queue<long int> coada;

	scanf("%ld %ld", &N, &M);
	vecini = new vector<long int> [N];
	grad = new long int[N];
	memset(grad, 0, sizeof(long int) * N);

	for (i = 0; i < M; ++i)
	{
		scanf("%ld %ld", &a, &b);
		vecini[a - 1].push_back(b - 1);
		grad[b - 1]++;
	}

	for (i = 0; i < N; ++i)
	{
		if(grad[i] == 0) coada.push(i);
	}
	coada.size();
	while(!coada.empty())
	{
		i = coada.front();
		printf("%ld ", i+1);
		for (int j = 0, length = vecini[i].size(); j < length; ++j)
		{
			if ((--grad[vecini[i][j]]) == 0)
				coada.push(vecini[i][j]);
		}
		coada.pop();
	}

	return 0;
}