拓扑排序(Topological Sorting)
By Long Luo
代码如下所示：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
32public 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)\)，其中 \(n\) 为字符串长度。
- 空间复杂度：\(O(V)\)。哈希表和字符串均需要存储 \(n\) 个元素。