## Old version of dfs1
##def dfs1(s, d, G):
##    step('s = ' + str(s))
##    if s == d: return True
##    if noChildren(s, G): return False
##    for n in children(s, G):
##        return dfs1(n, d, G)

def dfs1(s, d, G):
    step('s = ' + str(s))
    if noChildren(s, G): return False
    for n in children(s, G):
        if n == d: return True
        return dfs1(n, d, G)


def noChildren(s, G): 
    return not s in G

def children(s, G):
    return G[s]

def step(msg):
    raw_input(msg)

G = {'A':['B'], 'B':['D', 'C'], 'D':['E'], 'C':['E']}

print dfs1('A', 'E', G)

G2 = {'A':['B'], 'B':['A', 'D', 'C'], 'D':['E'], 'C':['E']}

print 'About to make a call that will cause a loop'
print dfs1('A', 'E', G2)