Cod sursa(job #897901)

Utilizator cprogrammer1994Cprogrammer cprogrammer1994 Data 27 februarie 2013 22:51:52
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstring>
#include <cstdio>
#include <cmath>

int n, m;

struct Line {
	int a;
	int b;
};

bool point[50001];
Line line[100001];

int t[50001];
int s;

bool slow_check(int p) {
	for (int i = 1; i <= m; ++i) {
		if (line[i].a == p) {
			return(false);
		}
	}
	return(true);
}

void deconnect(int p) {
	point[p] = true;
	for (int i = 1; i <= m; ++i) {
		if (line[i].b == p) {
			line[i--] = line[m--];
		}
	}
}

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) {
		fscanf(in, "%d%d", &line[i].a, &line[i].b);
	}

	s = n;

	while (s) {
		for (int i = 1; i <= n; ++i) {
			if (!point[i]) {
				if (slow_check(i)) {
					deconnect(i);
					t[s--] = i;
				}
			}
		}
	}

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

	fclose(in);
	fclose(out);
}