LeetCode 207. Course Schedule

题目

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