LeetCode 207. Course Schedule

Posted on | In |
Words count in article: 897 | Reading time ≈ 4

题目

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

1
2
3
4
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

1
2
3
4
5
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Constraints:

  • The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  • You may assume that there are no duplicate edges in the input prerequisites.
  • 1 <= numCourses <= 10^5

思路

即判断这些课程能否构成有向无环图（DAG），用拓扑排序。

方法一. 拓扑排序，DFS.

使用一个visited数组，当visited[i]值为0，说明还没判断这个点；当visited[i]值为1，说明当前的循环正在判断这个点；当visited[i]值为2，说明已经判断过这个点，含义是从这个点往后的所有路径都没有环，认为这个点是安全的。

对每个点出发都做这个判断，检查这个点出发的所有路径上是否有环，如果判断过程中找到了当前的正在判断的路径，说明有环；找到了已经判断正常的点，说明往后都不可能存在环，所以认为当前的节点也是安全的。如果当前点是未知状态，那么先把当前点标记成正在访问状态，然后找后续的节点，直到找到安全的节点为止。最后如果到达了无路可走的状态，说明当前节点是安全的。

时间复杂度是O(N ^ 2)，空间复杂度是O(N)。

方法二. 拓扑排序，BFS

每次选择入度为0的节点，作为序列的下一个节点，然后移除该节点和以该节点出发的所有边。

循环N次，这个循环次数并不是遍历节点的意思，而是我们如果正常取点的话，N次就能把所有的节点都取完了，如果N次操作结束还没判断出来，那么就不是DAG.在这N次中，每次都找一个入度为0的点，并把它的入度变为-1，作为已经取过的点不再使用，同时把从这个点指向的点的入度都-1.

这个过程中，如果找不到入度为0的点，那么说明存在环。如果N次操作，每次都操作成功的去除了一个入度为0的点，那么说明这个图是DAG.

时间复杂度是O(N ^ 2)，空间复杂度是O(N)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# # DFS
# class Solution(object):
#     def canFinish(self, numCourses, prerequisites):
#         """
#         :type numCourses: int
#         :type prerequisites: List[List[int]]
#         :rtype: bool
#         """
#         graph = collections.defaultdict(list)
#         for u, v in prerequisites:
#             graph[u].append(v)
        
#         # 0 = Unknown, 1 = visiting, 2 = visited
#         visited = [0] * numCourses
#         for i in range(numCourses):
#             if not self.dfs(graph, visited, i):
#                 return False
#         return True
    
    
#     def dfs(self, graph, visited, i):
#         if visited[i] == 1:
#             return False
#         if visited[i] == 2:
#             return True
#         visited[i] = 1
#         for j in graph[i]:
#             if not self.dfs(graph, visited, j):
#                 return False
#         visited[i] = 2
#         return True


# BFS
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        graph = collections.defaultdict(list)
        indegrees = collections.defaultdict(int)
        for u, v in prerequisites:
            graph[u].append(v)
            indegrees[v] += 1
        for i in range(numCourses):
            zerodegree = False
            for j in range(numCourses):
                if indegrees[j] == 0:
                    zerodegree = True
                    break
            if not zerodegree:
                return False
            indegrees[j] = -1
            for u in graph[j]:
                indegrees[u] -= 1
        return True