Cod sursa(job #695884)

Utilizator DSzprogDombi Szabolcs DSzprog Data 28 februarie 2012 15:23:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>

int n, m;
int notr[50002];
int indx[50002];
struct Con {
	unsigned short b, a;
} con[100002], depth[50002];

unsigned int * addr;
void qs(int l, int r) {
	int i = l;
	int j = r;
	unsigned int p = addr[(i + j) / 2];
	while (i <= j) {
		while (addr[i] < p) {++i;}
		while (addr[j] > p) {--j;}
		if (i <= j)	{
			unsigned int t = addr[i];
			addr[i] = addr[j];
			addr[j] = t;
			++i;
			--j;
		}
	}
	if (l < j) {qs(l, j);}
	if (i < r) {qs(i, r);}
}

void ls() {
	int k = 0;
	for (int i = 0; i < m; ++i) {
		if (k != con[i].a) {
			k = con[i].a;
			indx[k] = i;
		}
	}
}

void sign(int a, int d = 1) {
	if (depth[a].a < d) {
		depth[a].a = d;
		for (int i = indx[a]; con[i].a == a; ++i) {
			sign(con[i].b, d + 1);
		}
	}
}

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

	fscanf(in, "%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		fscanf(in, "%hu%hu", &con[i].a, &con[i].b);
		notr[con[i].b] = 1;
	}
	addr = (unsigned int *)con;
	qs(0, m - 1);
	ls();

	for (int i = 1; i <= n; ++i) {
		depth[i].b = i;
		if (!notr[i]) {
			sign(i);
		}
	}

	addr = (unsigned int *)depth;
	qs(1, n);

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

	fclose(in);
	fclose(out);
}