# Example graph from class notes
sampleGraph = {1:[2,3,4], 2:[1,3,5], 3:[1,2], 4:[1,7,9], 5:[2,9], 6:[9], 7:[4], 8:[9], 9:[5,8,6,4], 10:[11,12], 11:[10], 12:[10]}



# A global dictionary to store which nodes have been visited by dfs().
# This needs to be initialized before each call to dfs().
# We only care about the keys, not their values.  We're treating it as a set of nodes.
visited = {}

def dfs(graph,source,target):
    """Returns the target node, if it is connected via unvisited nodes to the source node in the graph; otherwise returns None."""
    if source in visited:
        # Already been here.  Don't try again.

        # print "We're looking at node",source
        
        return None

    else:
        # print "We're visiting node",source

        # Remember that we've come here.
        visited[source] = True

        if source == target:
            # Found it!  We're done.
            return target

        else:
            # Keep looking from where we're at.
            for node in graph[source]:
                result = dfs(graph,node,target)

                if result != None:
                    # Found it!  We're done.
                    return result

                # Otherwise, continue with the next node...

            # Not reachable from here via any edge.
            return None
    


# A version that initializes the global variable for us.
def startDFS(graph,source,target):
    """Returns the target node, if it is connected via unvisited nodes to the source node in the graph; otherwise returns None."""
    global visited      # Necessary.  Without this, Python thinks the next line creates a new local variable.
    visited = {}

    return dfs(graph,source,target)