SHARE
TWEET

Untitled

a guest Oct 12th, 2017 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public boolean canFinish(int numCourses, int[][] prerequisites) {
  2.     int[][] matrix = new int[numCourses][numCourses]; // i -> j
  3.     int[] indegree = new int[numCourses];
  4.    
  5.     for (int i=0; i<prerequisites.length; i++) {
  6.         int ready = prerequisites[i][0];
  7.         int pre = prerequisites[i][1];
  8.         if (matrix[pre][ready] == 0)
  9.             indegree[ready]++; //duplicate case
  10.         matrix[pre][ready] = 1;
  11.     }
  12.    
  13.     int count = 0;
  14.     Queue<Integer> queue = new LinkedList();
  15.     for (int i=0; i<indegree.length; i++) {
  16.         if (indegree[i] == 0) queue.offer(i);
  17.     }
  18.     while (!queue.isEmpty()) {
  19.         int course = queue.poll();
  20.         count++;
  21.         for (int i=0; i<numCourses; i++) {
  22.             if (matrix[course][i] != 0) {
  23.                 if (--indegree[i] == 0)
  24.                     queue.offer(i);
  25.             }
  26.         }
  27.     }
  28.     return count == numCourses;
  29. }
RAW Paste Data
Top