题解 | #体育课测验(一)#

检查图中是否有循环

1. 根据连接值得出邻接矩阵
2. 进行遍历图中的每一个节点,确认图中每个节点所在子树是否有连通 (1) 设置节点访问数组 visited 表示每个节点是否被访问过 (2) 设置节点路径数组 onPath 表示每个节点在某一颗子树中的访问情况,该数组是可回溯的,因为每个子树都是对所有子节点进行检测是否有环 (3) 递归路径遍历过程中,如果 visited[i] 或者 onPath[i] 出现重合则说明有环,返回 False (4) 对图中每个节点进行遍历,得出最终结果

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numProject int整型 
# @param groups int整型二维数组 
# @return bool布尔型
#
class Solution:
    def canFinish(self , numProject: int, groups: List[List[int]]) -> bool:
        # write code here
        graph = dict() 
        for i in range(numProject):
            graph[i] = []
        for s, e in groups:
            graph[s].append(e)
        onPath = [False for _ in range(numProject)]
        visited = [False for _ in range(numProject)]
        hasCyle = False
        def back(target):
            nonlocal hasCyle
            if onPath[target]:
                hasCyle = True
            if visited[target] or hasCyle:
                return
            onPath[target] = True
            visited[target] = True
            for n in graph[target]:
                back(n)
            onPath[target] = False
        for i in range(numProject):
            back(i)
            if hasCyle:
                return False
        return True