拓扑排序(Topological Sorting)

By Long Luo

207. 课程表

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
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
return true;
}

int[] indegree = new int[numCourses];
for (int[] pre : prerequisites) {
indegree[pre[0]]++;
}

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}

while (!queue.isEmpty()) {
Integer currId = queue.poll();
numCourses--;
for (int[] pre : prerequisites) {
if (pre[1] == currId) {
indegree[pre[0]]--;
if (indegree[pre[0]] == 0) {
queue.offer(pre[0]);
}
}
}
}

return numCourses == 0;
}

复杂度分析

  • 时间复杂度:O(V+E)O(V + E),其中nn为字符串长度。

  • 空间复杂度:O(V)O(V)。哈希表和字符串均需要存储nn个元素。

LeetCode 热题 HOT 100

参考资料

  1. Topological Sorting
  2. 拓扑排序