I am looking at GeeksforGeeks problem Cycle in a Directed Graph:

Given a Directed Graph with V vertices (Numbered from 0 to V−1) and E edges, check whether it contains any cycle or not.

The graph is represented as an adjacency list, where adj[i] contains a list of vertices that are directly reachable from vertex i. Specifically, adj[i][j] represents an edge from vertex i to vertex j.

Example 1:

Output: 1

Explanation: 3 -> 3 is a cycle.

My code

from typing import List

class Solution:
    
    # Function to detect cycle in a directed graph.
    def is_cyclic(self, adj : List[List[int]]) -> bool :
        def dfs(i, arr):
            vis[i] = 1
            for item in adj[i]:
                if not vis[item]:
                    arr.append(i)
                    if dfs(item,arr) == True:return True
                    arr.pop()
                else:
                    if item in arr:
                        return True
        n = len(adj)
        vis = [0]*n
        for i in range(n):
            if not vis[i]:
                if dfs(i,[i]) == True:
                    return True
        return False     

But this gives False for the example input while True is expected.

I changed the approach as to where to append nodes to the path arr like below, and then it worked, but I don't see why the above code wouldn't return the exact same results:

from typing import List

class Solution:
    
    # Function to detect cycle in a directed graph.
    def is_cyclic(self, adj : List[List[int]]) -> bool :
        def dfs(i, arr):
            vis[i] = 1
            arr.append(i)
            for item in adj[i]:
                if not vis[item]:
                    if dfs(item,arr) == True:
                        return True
                else:
                    if item in arr:
                        return True 
            arr.pop()
        n = len(adj)
        vis = [0]*n
        for i in range(n):
            if not vis[i]:
                if dfs(i,[]) == True:
                    return True
        return False    

The difference is only in the list that is passed to dfs. I don't understand why my code does not work properly as it essentially uses the same logic. What is my mistake?

I am looking at GeeksforGeeks problem Cycle in a Directed Graph:

Given a Directed Graph with V vertices (Numbered from 0 to V−1) and E edges, check whether it contains any cycle or not.

The graph is represented as an adjacency list, where adj[i] contains a list of vertices that are directly reachable from vertex i. Specifically, adj[i][j] represents an edge from vertex i to vertex j.

Example 1:

Output: 1

Explanation: 3 -> 3 is a cycle.

My code

from typing import List

class Solution:
    
    # Function to detect cycle in a directed graph.
    def is_cyclic(self, adj : List[List[int]]) -> bool :
        def dfs(i, arr):
            vis[i] = 1
            for item in adj[i]:
                if not vis[item]:
                    arr.append(i)
                    if dfs(item,arr) == True:return True
                    arr.pop()
                else:
                    if item in arr:
                        return True
        n = len(adj)
        vis = [0]*n
        for i in range(n):
            if not vis[i]:
                if dfs(i,[i]) == True:
                    return True
        return False     

But this gives False for the example input while True is expected.

I changed the approach as to where to append nodes to the path arr like below, and then it worked, but I don't see why the above code wouldn't return the exact same results:

from typing import List

class Solution:
    
    # Function to detect cycle in a directed graph.
    def is_cyclic(self, adj : List[List[int]]) -> bool :
        def dfs(i, arr):
            vis[i] = 1
            arr.append(i)
            for item in adj[i]:
                if not vis[item]:
                    if dfs(item,arr) == True:
                        return True
                else:
                    if item in arr:
                        return True 
            arr.pop()
        n = len(adj)
        vis = [0]*n
        for i in range(n):
            if not vis[i]:
                if dfs(i,[]) == True:
                    return True
        return False    

The difference is only in the list that is passed to dfs. I don't understand why my code does not work properly as it essentially uses the same logic. What is my mistake?

• python-3.x
• list
• recursion
• data-structures
• graph

Share Improve this question Follow edited Mar 11 at 22:48 daqh 14611 silver badge1212 bronze badges asked Mar 8 at 10:08 SwastikSwastik 1333 bronze badges

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

You are right in your general idea that it shouldn't matter whether you add the node to arr either at the start of dfs or just before dfs is called (and when in both cases you remove that node from arr again when that call returns without success).

However, you did not add the correct node in the version that fails the test.

In the first (failing) version, the node that should be added in the for loop should be the adjacent node being iterated, not i. So change this:

        for item in adj[i]:
            if not vis[item]:
                arr.append(i)  # <-- wrong node!

to this:

        for item in adj[i]:
            if not vis[item]:
                arr.append(item)  # <-- correct node

...and now also the first version of your code will work as expected.

Other remarks

Unrelated to your question, but evaluating the condition item in arr is not efficient. You could reduce the execution time for this condition by using vis for this purpose: use value 1 to indicate that the node is on the current path, and 2 that it is also visited, but no longer on the current path.

Also, you can make use of map and any to make your loops implicit. This results in this variant:

    def isCyclic(self, adj: List[List[int]]) -> bool:
        def dfs(i):
            if vis[i] == 1:
                return True
            vis[i] = 1
            if any(map(dfs, adj[i])):
                return True
            vis[i] = 2

        n = len(adj)
        vis = [0] * n
        return any(map(dfs, range(n)))