easily understand 9ms JAVA solution using BFS with topological sorting


  • 2
    F

    This solution is based on BFS and topological sorting algorithm.
    I was inspired a solution in Course Schedule, here is the problem: link text. But I can't find the solution now. I will add the link later. ^^
    We need an adjacent table to record the relationship between prerequisite course and current course.
    Also, we need an indegree table to record the number of courses we need to taken in order to take this current course.
    queue is to record the course with indegree 0, which means we can take this course immediately without limitation.
    Once we take the course with indegree 0, we can look up other courses which require this course as prerequisite and subtract their indegree by 1.
    Once the indegree is 0, add this course to the queue.
    before return, we need to check if there's a circle.

    public int[] findOrder(int numCourses, int[][] prerequisites) {
    // initialize an adjacent table
          List<Integer>[] adj = new List[numCourses];
          for(int i = 0; i < numCourses; i++){
              adj[i] = new ArrayList<Integer>();
          }
    // define an indegree table recording the number of prerequisite courses should be taken in order to take this current course
          int[] indegree = new int[numCourses];
          int[] result = new int[numCourses];
          for(int i = 0; i < prerequisites.length; i++){
              int preCourses = prerequisites[i][1];
              int curCourses = prerequisites[i][0];
              adj[preCourses].add(curCourses);
              indegree[curCourses]++;
          }
    // to find the course with indegree 0 (which we can take immediately)
          Queue<Integer> readyCourses = new LinkedList<Integer>();
          for(int i = 0; i < numCourses; i++){
              if(indegree[i] == 0){
                  readyCourses.offer(i);
              }
          }
          int count = 0;
    // if we take the course with indegree 0, we look up for the courses needing this course as prerequisite and subtract their indegree value by 1
          while(!readyCourses.isEmpty()){
              int ready = readyCourses.poll();
              result[count++] = ready;
              for(int nextCourse : adj[ready]){
                  indegree[nextCourse]--;
                  if(indegree[nextCourse] == 0){
                      readyCourses.offer(nextCourse);
                  }
              }
          }
    // to check if there's a circle-like requirements before return
          return count == numCourses ? result : new int[0];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.