Cod sursa(job #1066073)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 23 decembrie 2013 23:49:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<vector>
#include<iostream>
using namespace std;

#define MAXN 50100

int N, M, deg[MAXN], Q[MAXN], x, y;
vector<int> G[MAXN];

void read()
{
	cin >> N >> M;
	for(int i = 1; i <= M; ++i)
	{
		cin >> x >> y;
		G[x].push_back(y);
		deg[y]++;
	}
}

void topological_sort()
{
	int x;

	for(int i = 1; i <= N; ++i)
		if(deg[i] == 0)
			Q[++Q[0]] = i;

	for(int i = 1; i <= N; ++i)
	{
		x = Q[i];
		for(vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
		{
			deg[*it]--;
			if(deg[*it] == 0)
				Q[++Q[0]] = *it;
		}
	}
}

void print()
{
	for(int i = 1; i <= N; ++i)
		cout << Q[i] << " ";
}
	

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

	read();
	topological_sort();
	print();

	return 0;
}