210. Course Schedule II 发表于 2022-03-14 BFS12345678910111213141516171819202122232425262728293031323334353637383940class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { List<List<Integer>> edgeList = new ArrayList<>(numCourses); for (int i = 0; i < numCourses; i++) { edgeList.add(new ArrayList<>()); } int[] inDegrees = new int[numCourses]; for (int[] prerequisite : prerequisites) { int from = prerequisite[1], to = prerequisite[0]; inDegrees[to]++; edgeList.get(from).add(to); } Queue<Integer> zeroInDegreeCourseQueue = new LinkedList<>(); for (int i = 0; i < inDegrees.length; i++) { if (inDegrees[i] == 0) { zeroInDegreeCourseQueue.add(i); } } List<Integer> courseList = new ArrayList<>(); while (!zeroInDegreeCourseQueue.isEmpty()) { int course = zeroInDegreeCourseQueue.poll(); courseList.add(course); for (Integer to : edgeList.get(course)) { if (--inDegrees[to] == 0) { zeroInDegreeCourseQueue.add(to); } } } if (courseList.size() == numCourses) { return courseList.stream().mapToInt(Integer::intValue).toArray(); } else { return new int[0]; } }} DFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { List<List<Integer>> edgeList = new ArrayList<>(numCourses); for (int i = 0; i < numCourses; i++) { edgeList.add(new ArrayList<>()); } for (int[] prerequisite : prerequisites) { int from = prerequisite[1], to = prerequisite[0]; edgeList.get(from).add(to); } Stack<Integer> courseStack = new Stack<>(); int[] visitStatuses = new int[numCourses]; // 0: not visited, 1: visiting, 2: already visited for (int i = 0; i < numCourses; i++) { if (!dfs(edgeList, courseStack, i, visitStatuses)) { return new int[0]; } } int[] res = new int[courseStack.size()]; int index = 0; while (!courseStack.isEmpty()) { res[index++] = courseStack.pop(); } return res; } private boolean dfs(List<List<Integer>> edgeList, Stack<Integer> courseStack, int course, int[] visitStatuses) { if (visitStatuses[course] == 2) { return true; } if (visitStatuses[course] == 1) { return false; } visitStatuses[course] = 1; for (int to : edgeList.get(course)) { if (!dfs(edgeList, courseStack, to, visitStatuses)) { return false; } } visitStatuses[course] = 2; courseStack.push(course); return true; }} Reference210. Course Schedule II