#Problem

#⭐️⭐️

Course Schedule II

#Solution

Topological Sort

还是用DFS方便. 详见下面的code.

#Code

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// 太慢了!
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
final int[] res = new int[numCourses];
if (numCourses == 0) {
return res;
}
if (prerequisites.length == 0) {
for (int i = 0; i < numCourses; i++) {
res[i] = i;
}
return res;
}
final Stack<Integer> stack = new Stack<>();
final Map<Integer, Set<Integer>> graph = new HashMap<>();
final Map<Integer, Integer> indegree = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new HashSet<>());
indegree.put(i, 0);
}
for (final int[] edge : prerequisites) {
graph.get(edge[0]).add(edge[1]);
indegree.merge(edge[1], 1, Integer::sum);
}
final Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree.get(i) == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
final int front = queue.poll();
stack.push(front);
for (final int adj : graph.get(front)) {
indegree.merge(adj, -1, Integer::sum);
if (indegree.get(adj) == 0) {
queue.offer(adj);
}
}
}
for (int i = 0; i < numCourses; i++) {
if (indegree.get(i) != 0 ){
return new int[0];
}
}
for (int i = 0; i < numCourses; i++) {
res[i] = stack.pop();
}
return res;
}
}
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
final int[] res = new int[numCourses];
if (numCourses == 0) return res;
if (prerequisites.length == 0) {
for (int i = 0; i < numCourses; i++) res[i] = i;
return res;
}
final Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < numCourses; i++) graph.put(i, new HashSet<>());
for (final int[] edge: prerequisites) graph.get(edge[0]).add(edge[1]);
final Queue<Integer> queue = new LinkedList<>();
final int[] visited = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0) {
if (dfsTopoSort(i, graph, visited, queue)) {
return new int[0];
}
}
}
for (int i = 0; i < numCourses; i++) {
res[i] = queue.poll();
}
return res;
}
private boolean dfsTopoSort(final int v, final Map<Integer, Set<Integer>> graph, final int[] visited, final Queue<Integer> queue) {
if (visited[v] == -1) return true;
if (visited[v] == 1) return false;
visited[v] = -1;
for (final int adj : graph.get(v)) {
if (dfsTopoSort(adj, graph, visited, queue)) {
return true;
}
}
visited[v] = 1;
queue.offer(v);
return false;
}
}

Comments