Cod sursa(job #206572)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 7 septembrie 2008 19:58:49
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <stdio.h>
#include <vector>

using namespace std;

const int N_MAX = 50010;

vector <int> G[N_MAX];
int gr[N_MAX];

int q[N_MAX], in = 1, sf = 1;

int main()
{
	freopen("sortaret.in", "r", stdin);
#ifndef _SCREEN_
	freopen("sortare.out", "w", stdout);
#endif

	int N, M, x, y;

	scanf("%d %d\n", &N, &M);
	for (int i = 1; i <= M; i ++) {
		scanf("%d %d\n", &x, &y);
		gr[y] ++;
		G[x].push_back(y);
	}

	for (int i = 1; i <= N; i ++) {
		if (gr[i] == 0) q[sf ++] = i;
	}

	while (in < sf) {
		int nod = q[in];
		in ++;
		printf("%d ", nod);

		for (vector <int>::iterator it = G[nod].begin(); it != G[nod].end(); ++ it) {
			gr[*it] --;
			if (gr[*it] == 0) q[sf ++] = *it;
		}
	}
	printf("\n");

	return 0;
}