有向图环检测DFS代码返回错误结果，求问题原因

我正在解决GeeksforGeeks上的「有向图中的环」问题：给定含V个顶点（编号0到V-1）和E条边的有向图，判断是否存在环，图以邻接表adj表示，adj[i]是顶点i可直接到达的顶点列表。

示例1存在3->3的自环，预期输出为1（True），但第一段代码返回False。修改路径数组arr的添加位置后，第二段代码运行正确，疑惑两段逻辑看似一致，错误原因是什么？

第一段代码（错误） #

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     

第二段代码（正确） #

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    

错误原因分析 #

两段代码的核心差异在于路径数组arr的更新时机，这直接影响了环检测的准确性：

第一段代码的逻辑缺陷 #

1. 路径记录不完整：仅在访问未被标记的邻接点时，才将当前节点加入arr。这导致arr无法准确记录当前的递归路径，它存储的是父节点的重复值，而非实际的路径节点序列。
2. 初始路径的错误弥补：初始调用时传入[i]试图手动初始化路径，但这种方式无法覆盖所有场景。比如：
   • 当节点存在自环时，虽然初始arr包含该节点，但如果节点有多个邻接点，处理完其他邻接点后arr被弹出修改，可能导致后续环检测失效；
   • 更关键的是，这种逻辑违背了递归路径跟踪的基本规则——应该在进入节点时立即加入路径，离开时回溯弹出。

第二段代码的正确逻辑 #

• 进入即记录路径：进入dfs函数后立即将当前节点加入arr，确保arr始终准确反映当前的递归路径。
• 回溯时弹出节点：处理完当前节点的所有邻接点后，将当前节点从arr中弹出，保证路径跟踪的正确性。
• 初始路径为空：无需手动初始化路径，进入节点时会自动添加当前节点，符合递归的自然流程。

这种正确的路径跟踪方式，无论是自环、简单环还是复杂环，都能准确检测到邻接点是否存在于当前递归路径中，从而正确判断图中是否存在环。

内容的提问来源于stack exchange，提问作者Swastik