拓扑排序。Time = O(V+E), Space = O(V+E),V为点数,E为边数,拓扑排序仅遍历所有的点和边一次。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
Map<Integer, List<Integer>> map = new HashMap<>();
int[] coursesByOrder = new int[numCourses];
int index = 0;
for (int i = 0; i < prerequisites.length; i++) {
indegree[prerequisites[i][0]]++;
map.put(prerequisites[i][1], map.getOrDefault(prerequisites[i][1], new ArrayList<>()));
map.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
coursesByOrder[index++] = i;
}
}
while (!queue.isEmpty()) {
int curCourse = queue.poll();
List<Integer> subCourses = map.get(curCourse);
if (subCourses != null) {
for (int subCourse : subCourses) {
if (--indegree[subCourse] == 0) {
queue.offer(subCourse);
coursesByOrder[index++] = subCourse;
}
}
}
}
if (index != numCourses) {
return new int[0];
}
return coursesByOrder;
}
}