<jupyter_start><jupyter_text>你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。    在选修某些课程之前需要一些先修课程。     例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]    给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？示例 1:    输入: 2, [[1,0]]     输出: true    解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。示例 2:    输入: 2, [[1,0],[0,1]]    输出: false    解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。提示：    输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。    你可以假定输入的先决条件中没有重复的边。    1 <= numCourses <= 10^5<jupyter_code>from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites):
        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[a].append(b)
        
        # 从任意一门课开始，只要能够完成的课 >= prerequisites
        total = set() 
        for i in range(numCourses):
            seen = set() # 从这门课开始
            q = deque()
            q.append(i)
            while q:
                q_len = len(q)
                for _ in range(q_len):
                    n = q.pop()
                    if n not in seen: 
                        seen.add(n) # 学习了 n 这门课
                        print(n, seen)
                        for j in graph[n]: # 学习 n 这门课之前，应该学习哪些课程
                            if j in seen: # 不能构成闭环
                                return False
                            if len(seen) >= numCourses:
                                return True
                            q.append(j)
            total |= seen
            if len(total) >= numCourses:
                return True
        return True if len(total) >= numCourses else False
from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites):
        indeg = [0] * numCourses # 统计学习一门课之前，需要学习课程的数量
        edges = defaultdict(list)
        for x, y in prerequisites:
            edges[y].append(x)
            indeg[x] += 1
        
        result = 0
        # 首先学习哪些不需要前导课程的课
        q = deque([u for u in range(numCourses) if indeg[u] == 0])
        while q:
            u = q.popleft()
            result += 1 # 学习了一门课
            for i in edges[u]: # 只有学习了课程 u 才能进行学习的其他课程
                indeg[i] -= 1
                if indeg[i] == 0:
                    q.append(i)
        return result == numCourses
from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites):
        # visited == 0: 没有探索 1： 正在探索 2：探索过了
        def dfs(u):
            nonlocal result, invalid
            visited[u] = 1
            for v in graph[u]:
                if visited[v] == 0:
                    if invalid:
                        return 
                    dfs(v)
                elif visited[v] == 1: # 形成了环
                    invalid = True
                    return
            visited[u] = 2
            result += 1
        
        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a) # 需要先学习 b 的课程有 a
        visited = [0] * numCourses
        result = 0
        invalid = False
        
        for i in range(numCourses):
            if invalid is False and visited[i] == 0:
                dfs(i)
        return result == numCourses
solution = Solution()
solution.canFinish(3, [[0,1],[0,2],[1,2]])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0940998487140696, 'fraction_numerical': 0.016036308623298034, 'mean_word_length': 1.4202049780380674, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '609552', 'license': 'Apache-2.0', 'n_tokens_mistral': 1315, 'n_tokens_neox': 1337, 'n_words': 285, 'path': 'Graph/1115/207. Course Schedule.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '3305'}