课程表

2025/10/16

思路：就是判断是否是有向无环图。从任意节点DFS，看看能不能重复到自己，如果能则不行；DFS完了之后，再从课程表里选还没DFS访问过的，继续DFS。

def DFS(course, prerequisites, one_round_visited, visited):

    one_round_visited[course] = True
    visited[course] = True
    
    for i in prerequisites:
        if prerequisites[i][0] == course:
            if one_round_visited[prerequisites[i][1]] == True: return False
            DFS(prerequisites[i][0])
    return True

def canFinish(numCourses, prerequisites):

    visited = [False] * numCourses

    for course in range(numCourses):
        one_round_visited = [False] * numCourses
        if visited[course] == False:
            ring_exists = DFS(course, prerequisites, one_round_visited, visited)
            if ring_exists:
                return False
            
    return True

答案：完全正确，秒了