#!/usr/bin/python
# Hey Python, this file is in coding: utf8

# DFS /ohne/ Stack

#------------------------------------------------------------------------------#
def dfs(G):
	nodes = G.keys()
	nodes.sort()

	pi = {}
	d = {}
	f = {}
	col = {}
	time = 0

	for u in nodes:
		col[u] = "weiß"

	for u in nodes:
		if col[u] == "weiß":
			col[u] = "grau"
			pi[u] = None
			d[u] = time
			time += 1

			while u != None:
				next = None
				for v in G[u]:
					if col[v] == "weiß":
						pi[v] = u
						col[v] = "grau"
						d[v] = time
						time += 1
						next = v
						break

				if next:
					u = next
				else:
					col[u] = "schwarz"
					f[u] = time
					time += 1
					u = pi[u]

	return (pi,d,f)
#------------------------------------------------------------------------------#

if __name__ == "__main__":
	G = { 1:[2],
		  2:[3,4],
		  3:[6,4],
		  4:[],
		  5:[1,6],
		  6:[] }

	(pi,d,f) = dfs(G)
	
	nodes = G.keys()
	nodes.sort()

	for u in nodes:
		print "pi[%(node)3d] = %(pi)5s    d[%(node)3d] = %(d)3d    f[%(node)3d] = %(f)3d" % \
				{"node":u, "pi":pi[u], "d":d[u], "f":f[u]}

# vim: sw=4 ts=4 foldmethod=marker fileformat=unix :