Twibet: a recursive solution in Ptyhon

Today a friend told me she's struggling with solving the EuroPython 2011 Problem D, called Twibet. I wrote a quick solution and I'm publishing it here for those who are curious about it.
The key to my solution was the recursive traversal (traverse_graph) of a directed graph. The representation of the graph is a dictionary of the monks as keys and a list of the following monks as values.
Because running on the large input file raised a runtime error of  maximum recursion depth exceeded, I used a this little hack: sys.setrecursionlimit(10000).
UPDATE: Here are the solutions of the contestants.

	'''
	this is a solution of the EuroPython 2011 Problem D. Twibet
	http://code.google.com/codejam/contest/dashboard?c=1277486#s=p3
	'''
	def build_graph(input_list):
	di = {}
	for i in range(1, len(input_list)+1):
	di[i] = []
	for monk, followed_monk in enumerate(input_list, start=1):
	di[followed_monk].append(monk)
	return di
	def traverse_graph(graph, start, monks_today):
	monks_today.add(start)
	result = 1
	result += sum(map(lambda monk: traverse_graph(graph, monk, monks_today), \
	filter(lambda monk : monk not in monks_today, graph[start])))
	return result
	def solve_case(case_no, line):
	print "Case #%i:" % case_no
	input_list = map(int, line.split())
	for monk in range(1, len(input_list)+1):
	print traverse_graph(build_graph(input_list), monk, set())
	def main():
	import sys
	sys.setrecursionlimit(10000)
	lines = sys.stdin.readlines()
	for case_no, line in enumerate(lines[2::2], start=1):
	solve_case(case_no, line.strip())
	main()

view raw twibet.py hosted with ❤ by GitHub