In [37]:

    

def findCycles(G, node, visited=set(), processed={}):
    visited.add(node)
    processed[node] = False

    for neighbor in G[node]:
        if neighbor not in visited:
            if findCycles(G, neighbor, visited, processed): 
                return True
        elif not processed[neighbor]:
            # if we're discovered, but not processed, it's a back edge
            # because it means we've recursed down this node at some point
            # (and thus its an ancestor), but somehow ended back here
            print "back edge found", node, "->", neighbor   
            return True
            
    processed[node] = True
    return False
        
def main():
    G = {0: [1, 3], 1: [2], 2: [], 3: [1, 4], 4: [0]}
    print findCycles(G, 0)
    
if __name__ == "__main__":
    main()


    

    




back edge found 4 -> 0
True

In [ ]: