Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Your runtime beats 37.07 % of java submissions.
- class Solution {
- public int[] findOrder(int numCourses, int[][] prerequisites) {
- int[] dc = new int[numCourses];
- ArrayList<ArrayList<Integer>> deps = new ArrayList<ArrayList<Integer>>();
- for (int i = 0; i < numCourses; i++) {
- deps.add(new ArrayList<Integer>());
- }
- for (int[] req: prerequisites) {
- deps.get(req[1]).add(req[0]);
- dc[req[0]] += 1;
- }
- List<Integer> res = new ArrayList<>();
- while (res.size() < numCourses){
- boolean f = false;
- for (int node = 0; node < numCourses; node++) {
- if (dc[node] == 0) {
- dc[node] = -1;
- for (int d: deps.get(node)) dc[d] -= 1;
- res.add(node);
- f = true;
- }
- }
- if (!f) return new int[0];
- }
- int[] result = new int[numCourses];
- for (int i = 0; i < numCourses; i++) result[i] = res.get(i);
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement