source.c

#include <stdio.h>
#include <stdlib.h>

#define MAX(a,b) (((a)>(b))?(a):(b))

int N;

typedef struct Exit {
	struct Stage * stage;
	struct Exit * nextExit;
} tExit;

typedef struct Stage {
	int id;
	int cleared;
	struct Exit * exits;
} tStage;

tStage stages[1001];

int maxPlay(tStage * stage) {
	if (stage->cleared) return 0;
	stage->cleared = 1;

	int minutes = 1;
	int x = 0;
	int y = 0;


	tExit * e = stage->exits;
	while (e) {
		y = maxPlay(e->stage);
		x = MAX(x,y);
		e = e->nextExit;
	}
	minutes += x;
	return minutes;
}

void resetStages() {
	for(int i = 0; i <= 1001; i++) {
		stages[i].id = i;
		stages[i].cleared = 0;
		stages[i].exits = 0;
	}
}

tExit * newExit(tStage * stage) {
	tExit * e = malloc(sizeof(tExit));
	e->nextExit = 0;
	e->stage = stage;
	return e;
}

void appendExit(tStage * from, tStage * to) {
	tExit * e = from->exits;

	if (e) {
		while (e->nextExit) {
			e = e->nextExit;
		}
		e->nextExit = newExit(to);
	} else {
		from->exits = newExit(to);
	}
}

void freeExits(tStage * stage) {
	tExit * e = stage->exits;
	tExit * n;
	while (e) {
		n = e->nextExit;
		free(e);
		e = n;
	}
}

int main() {

	int T, test_case, i;
	int from, to;

	// freopen function below opens input file in read only mode, and afterward,
	// the program will read from input file instead of standard(keyboard) input.
	// To test your program, you may save input data in input file,
	// and use freopen function to read from the file when using scanf function.
	// You may remove the comment symbols(//) in the below statement and use it.
	// But before submission, you must remove the freopen function or rewrite comment symbols(//).
	freopen("sample_input.txt", "r", stdin);

	// If you remove the statement below, your program's output may not be recorded
	// when your program is aborted due to the time limit.
	// For safety, please use setbuf(stdout, NULL); statement.
	setbuf(stdout, NULL);

	scanf("%d", &T);
	for (test_case = 1; test_case <= T; ++test_case) {
		resetStages();

		// Read each test case from standard input.
		scanf("%d", &N);
		for (i = 1; i <= N - 1; i++) {
			scanf("%d %d", &from, &to);
			appendExit(&stages[from], &stages[to]);
		}

		//////////////////////////////////////////////////////////
		// Implement your algorithm from this section.        	//
		//////////////////////////////////////////////////////////
		printf("#%d %d\n", test_case, maxPlay(&stages[1]));

		for (i = 1; i <= N - 1; i++) {
			freeExits(&stages[i]);
		}
	}
	return 0;
}