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. OK, I Understand
 
Top