Cod sursa(job #261391)

Utilizator CezarMocanCezar Mocan CezarMocan Data 18 februarie 2009 10:37:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#define maxn 51000

long n, m, i, j, a, b;
long list[100010];
long nr[maxn], grad[maxn], q[maxn];

void sortaret() {
	long i, j, k, nod;
	for (i = 1; i <= n; i++) {
		if (grad[i] == 0) {
			q[0]++;
			q[q[0]] = i;
		}
	}
	i = 1;
	while (i <= q[0]) {
		nod = q[i];
		printf("%d ", nod);
		for (j = nr[nod - 1] + 1; j <= nr[nod]; j++) {
			grad[list[j]]--;
			if (grad[list[j]] == 0) {
				q[0]++;
				q[q[0]] = list[j];
			}

		}
		i++;
	}
}

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

	scanf("%ld %ld ", &n, &m);

	for (i = 1; i <= m; i++) {
		scanf("%d%d", &a, &b);
		nr[a]++;
	}

	for (i = 1; i <= n; i++)
		nr[i] += nr[i - 1];

	fclose(stdin);
	freopen("sortaret.in", "r", stdin);

	scanf("%ld %ld ", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%ld %ld ", &a, &b);
		q[a]++;
		list[nr[a - 1] + q[a]] = b;
		grad[b]++;
	}

	for (i = 1; i <= n; i++)
		q[i] = 0;
	sortaret();


	return 0;
}