• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Sep 23rd, 2019 96 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. // Runtime: 76 ms, faster than 5.08% of Java online submissions for Course Schedule II.
2. // Memory Usage: 48.5 MB, less than 8.54% of Java online submissions for Course Schedule II.
3. class Solution {
4.     public int[] findOrder(int numCourses, int[][] prerequisites) {
5.         boolean[][] g = new boolean[numCourses][numCourses];
6.         for (int[] req: prerequisites) g[req[0]][req[1]] = true;
7.
8.         int[] depths = new int[numCourses];
9.         boolean[] visited = new boolean[numCourses];
10.         try {
11.             for (int v = 0; v < numCourses; v++) findDepth(v, numCourses, g, depths, visited);
12.         }
13.         catch (IllegalStateException e) {
14.             return new int[0];
15.         }
16.
17.         List<Integer> res = new ArrayList<>();
18.         for (int v = 0; v < numCourses; v++) res.add(v);
19.
20.         Collections.sort(res, (a, b) -> depths[a] - depths[b]);
21.
22.         int[] result = new int[numCourses];
23.         for (int i = 0; i < numCourses; i++) result[i] = res.get(i);
24.         return result;
25.     }
26.
27.     private int findDepth(int v, int numCourses, boolean[][] g, int[] depths, boolean[] visited) {
28.         if (depths[v] > 0) return depths[v];
29.
30.         if (visited[v]) throw new IllegalStateException();
31.
32.         visited[v] = true;
33.
34.         int maxChildDepth = 0;
35.         for (int t = 0; t < numCourses; t++) {
36.             if (t == v) continue;
37.             if (!g[v][t]) continue;
38.
39.             maxChildDepth = Math.max(maxChildDepth, findDepth(t, numCourses, g, depths, visited));
40.         }
41.
42.         visited[v] = false;
43.
44.         int depth = maxChildDepth + 1;
45.         depths[v] = depth;
46.         return depth;
47.     }
48. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top