Cod sursa(job #897979)

Utilizator cprogrammer1994Cprogrammer cprogrammer1994 Data 27 februarie 2013 23:31:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstring>
#include <cstdio>
#include <cmath>

struct Elem {
	int value;
	Elem * next;
	Elem(int v, Elem * n) {
		value = v;
		next = n;
	}
};

int n, m;
int count[50001];
Elem * elem[50001];

int s;
int t[50001];

int main() {
	FILE * in = fopen("sortaret.in", "rt");
	FILE * out = fopen("sortaret.out", "wt");

	fscanf(in, "%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int a, b;
		fscanf(in, "%d%d", &a, &b);
		elem[a] = new Elem(b, elem[a]);
		++count[b];
	}

	for (int i = 1; i <= n; ++i) {
		if (!count[i]) {
			t[++s] = i;
		}
	}

	for (int i = 1; i <= n; ++i) {
		Elem * e = elem[t[i]];
		while (e) {
			--count[e->value];
			if (!count[e->value]) {
				t[++s] = e->value;
			}
			e = e->next;
		}
	}

	for (int i = 1; i <= s; ++i) {
		fprintf(out, "%d ", t[i]);
	}

	fclose(in);
	fclose(out);
}