Problem

Given an undirected graph, determine whether it contains a cycle.
Input:
The input to the function/method consists of two arguments:
g: a list of list of integers, denoting the adjacency list representation of the graph.
Output:
Return 1 if the graph contains a cycle, otherwise return 0.
Example:
Input:
g: [[1,2],[2,3],[3,4],[4,1]]
Output:
1

Solution

# Solution:
# The solution is to use a depth first search algorithm to traverse the graph.
# If a node is visited twice, then there is a cycle.
# The solution is optimal because it only traverses the graph once.

def has_cycle(g):
    visited = set()
    for node in g:
        if node not in visited:
            if dfs(node, visited, None):
                return 1
    return 0

def dfs(node, visited, parent):
    visited.add(node)
    for neighbor in node:
        if neighbor not in visited:
            if dfs(neighbor, visited, node):
                return True
        elif neighbor != parent:
            return True
    return False