207. Course Schedule

Approach I** 广度优先搜索
使用长度拓扑排序 - 图1的数组记录每个节点的入度，依次将入度为拓扑排序 - 图2的节点入队；图的存储使用邻接表**。

  1. class Solution:
  2.     def canFinish(self, n: int, requisites: List[List[int]]) -> bool:
  3.         indegrees = [0] * n                 # 入度
  4.         adjacency = [[] for _ in range(n)]  # 或者直接使用 collections.defaultdict(list)
  6.         for cur, pre in requisites:
  7.             indegrees[cur] += 1
  8.             adjacency[pre].append(cur)
  10.         queue = collections.deque()         # 可用一行'列表生成式'直接建立入度为0的队列
  11.         for i, indegree in enumerate(indegrees):
  12.             if indegree == 0:
  13.                 queue.append(i)
  15.         while queue:
  16.             pre = queue.popleft()
  17.             n -= 1
  18.             for cur in adjacency[pre]:
  19.                 indegrees[cur] -= 1
  20.                 if indegrees[cur] == 0:
  21.                     queue.append(cur)
  23.         return n == 0
  • 时间复杂度：拓扑排序 - 图3，需要访问所有节点和所有临边
  • 空间复杂度：拓扑排序 - 图4，邻接表有拓扑排序 - 图5个节点，拓扑排序 - 图6条边；队列空间最长为拓扑排序 - 图7

Approach II** 深度优先搜索**
使用states记录每个节点的搜索状态：

  • 拓扑排序 - 图8，还未被访问；
  • 拓扑排序 - 图9，被当前节点出发的dfs访问；
  • 拓扑排序 - 图10，已经被其他节点出发的dfs访问。 ```python from collections import defaultdict

class Solution: def canFinish(self, n: int, requisites: List[List[int]]) -> bool: def dfs(i): if states[i] == 1: # 被当前节点出发的路径’重复’访问，存在环 return False if states[i] == -1: return True

  1.         states[i] = 1
  2.         for j in edges[i]:
  3.             if not dfs(j):
  4.                 return False
  5.         states[i] = -1
  6.         return True
  8.     states = [0] * n               # 0:未访问，1: 被当前节点访问，-1:已被其他节点访问
  9.     edges = defaultdict(list)      # 邻接表
  10.     for cur, pre in requisites:
  11.         edges[pre].append(cur)
  13.     for i in range(n):
  14.         if not dfs(i):
  15.             return False
  16.     return True

- 时间复杂度：![](https://cdn.nlark.com/yuque/__latex/b6ff3b690fec561173ab1476b1afe331.svg#card=math&code=O%28n%20%2B%20m%29&id=mmLOl)，需要访问所有**节点**和所有**临边**
- 空间复杂度：![](https://cdn.nlark.com/yuque/__latex/b6ff3b690fec561173ab1476b1afe331.svg#card=math&code=O%28n%20%2B%20m%29&id=tmmNm)，邻接表有![](https://cdn.nlark.com/yuque/__latex/e65a67ac353abeeff44c359310d05c02.svg#card=math&code=O%28n%29&id=F3vYG)个**节点**，![](https://cdn.nlark.com/yuque/__latex/647835a0fd65141186ae53da33070f1b.svg#card=math&code=O%28m%29&id=rlsRv)条**边**；**递归栈**空间最深为![](https://cdn.nlark.com/yuque/__latex/e65a67ac353abeeff44c359310d05c02.svg#card=math&code=O%28n%29&id=ILDB7)

<a name="iBDRJ"></a>
#### [210. Course Schedule II](https://leetcode-cn.com/problems/course-schedule-ii/)
```python
class Solution:
    def findOrder(self, N: int, requisites: List[List[int]]) -> List[int]:
        res = []
        edges = collections.defaultdict(list)
        indegrees = [0] * N

        for cur, pre in requisites:
            indegrees[cur] += 1
            edges[pre].append(cur)

        # 存放入度为0的节点
        queue = collections.deque([i for i in range(N) if indegrees[i] == 0])
        while queue:
            pre = queue.popleft()
            res.append(pre)
            for cur in edges[pre]:
                indegrees[cur] -= 1
                if indegrees[cur] == 0:
                    queue.append(cur)

        if len(res) != N:
            return []
        return res
  • 时间复杂度：拓扑排序 - 图11，需要访问所有节点和所有临边
  • 空间复杂度：拓扑排序 - 图12，邻接表有拓扑排序 - 图13个节点，拓扑排序 - 图14条边；队列空间最长为拓扑排序 - 图15