The title

Train of thought

  • Depending on the dependencies between coursesBuild a directed graphwithList<List<Integer>>Integer indicates the course number.
    • If there are loops in the graph, cyclic dependencies exist and return false
  • At the same time of building the graph statistics of each node in the graph, generate the entry table inDegree
  • Maintains a queue that represents classes that do not currently require a pre-course to start, i.e., willAll nodes whose degree of entry is 0 are added to the queue
    • For every class in queue, count + 1 adds the class to the result set res
    • If queue is not empty, count the first queue node as curCourse, then count all its successors as adjCourse -1
    • If there are loops, there must be classes that are never zero and can never be added to the queue. So, when queue is empty, count will not equal the total number of courses, and there is no such sequence, return [].

code

// use 0,1,2... Said numCourse - 1
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];/ / the result set
        List<List<Integer>> graph = new ArrayList<>();/ / figure
        int[] inDegree = new int[numCourses];/ / into the table
        // Initialize the list of successors to each course
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        // Create a directed graph and update the entry table
        for (int[] arr : prerequisites) {
            graph.get(arr[1]).add(arr[0]);// Add a successor to the current course to the list
            inDegree[arr[0]] + +;// Subsequent courses gain +1
        }
        // Initializes the learnable courses queue
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {// I represents courses from 0 to Coursenum-1
            if (inDegree[i] == 0) {
                queue.add(i);// find all courses with an entry degree of 0 and join the queue}}int count = 0;// The number of courses completed
        // Take a course out of the cohort and update the entry table
        while(! queue.isEmpty()) {int curCourse = queue.removeFirst();
            res[count] = curCourse;// Add the lessons learned to the result set
            count++;
            for (int adjCourse : graph.get(curCourse)) {//adjCourse is the successor of the current course
                inDegree[adjCourse]--;// After completing the current course, the following course will have a -1 degree
                if (inDegree[adjCourse] == 0) {// Join the learnable queue if the enrollment of subsequent courses is also 0queue.add(adjCourse); }}}return count == numCourses ? res : new int[0];// If not, return []}}Copy the code