课程表-526互联

# 使用深度搜索栈的方式实现
class Solution:
    def canFinish(self, numCourses, prerequisites):
        # 构建图的邻接表
        self.graph = {i: [] for i in range(numCourses)}
        for edge in prerequisites:
            course, pre_course = edge
            self.graph[pre_course].append(course)

        # 记录节点的访问状态，0: 未访问, 1: 正在访问, -1: 已访问
        self.visited = [0] * numCourses

        def has_cycle(course):
            stack = [(course, 0)]

            while stack:
                current_course, state = stack.pop()

                if state == 0:
                    # 标记为正在访问
                    self.visited[current_course] = 1
                    stack.append((current_course, 1))

                    # 将邻居节点入栈
                    for neighbor in self.graph[current_course]:
                        if self.visited[neighbor] == 0:
                            stack.append((neighbor, 0))
                        elif self.visited[neighbor] == 1:
                            return True  # 遇到正在访问中的节点，说明存在环
                else:
                    # 标记为已访问
                    self.visited[current_course] = -1

            return False

        # 对每个未访问的节点进行深度搜索
        for i in range(numCourses):
            if self.visited[i] == 0:
                if has_cycle(i):
                    return False  # 存在环，无法完成所有课程的学习

        return True  # 无环，可以完成所有课程的学习

# 示例
solution = Solution()
numCourses = 2
prerequisites = [[1, 0], [0, 1]]
result = solution.canFinish(numCourses, prerequisites)
print(result)  # 输出 True