Cod sursa(job #1341719)

Utilizator aimrdlAndrei mrdl aimrdl Data 13 februarie 2015 00:50:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <stdio.h>
#include <string.h>

#define INCR 20
#define WHITE 0
#define GREY 1
#define BLACK 2

struct node {
	int n;
	int crt;
	int max;
	node **next;
	
	void init (int i);
};

void node::init (int i) {
	n = i;
	crt = 0;
	max = INCR;
	next = new node *[INCR];
}
	
void increase (node *N) {
	N->max += INCR;
	node **temp = new node *[N->max];
	memcpy(temp, N->next, N->crt * sizeof(node *));
	N->next = temp;
}	

void add (node *N, int i, int j) {
	if (N->crt == N->max) {
		increase(N);
	}
	
	N[j].next[N[j].crt] = &N[i];
	++(N[j].crt);
}
	
	
	 
int read(FILE *in, node **N) {
	int n, m;
	fscanf(in, "%d %d", &n, &m);
	
	node *temp = new node[n];
	for (int i = 0; i < n; i++) {
		temp[i].init(i+1);
	}
	
//	add(temp, n-1, m-1);
	
	for (int i = 0; i < m; i++) {
		int x, y;
		fscanf(in, "%d %d", &x, &y);
		add(temp, x-1, y-1);
	}
	
	*N = temp;
	
	return n;
}

void intest	(node *N, int n) {
	for (int i = 0; i < n; i++) {
		printf("%d: ", N[i].n);
		for (int j = 0; j < N[i].crt; j++) {
			printf("%d ", N[i].next[j]->n);
		}
		printf("\n");
	}
}

void visit(node *n, short *color, node **sorted, int *crt) {
	color[n->n-1] = GREY;
	for (int i = 0; i < n->crt; i++) {
		if (color[n->next[i]->n-1] == WHITE) {
			visit(n->next[i], color, sorted, crt);
		}
	}
	color[n->n-1] = BLACK;
	sorted[*crt] = n;
	(*crt)++;
}
	
	

void tsort (node *N, node **sorted, int n) {
	int crt = 0;
	short color[n+1];
	memset(color, 0, (n+1) * sizeof(short));
	for (int i = 0; i < n; i++) {
		if (color[i] == WHITE) {
			visit(&N[i], color, sorted, &crt);
		}
	}
}	
	
	
int main (void) {
	FILE *in = fopen("sortaret.in", "r");
	FILE *out = fopen("sortaret.out", "w");
	
	node *N;
	int n = read(in, &N);
	//intest(N, n);
	node **sorted = new node *[n];
	tsort(N, sorted, n);
	
	for (int i = 0; i < n; i++) {
		fprintf(out, "%d ", sorted[i]->n);
	}
	printf("\n");
	
	return 0;
}