210. Course Schedule II

[songyy5517]

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Intuition Considering each course as a node, the prerequisite between them is an edge, this problem is basically a topological sorting problem. Therefore, we can employ Kanh's Algorithm to solve this problem.

[songyy5517]

Approach: Kanh

1. Exception handling;
2. Define variables;
   • Queue<Integer> queue: stores the nodes with in-degree 0;
   • int[] degree: records the degree of each node;
   • int[] res: the final sorting result;
   • count = 0: the number of sorted nodes;
3. Calculate the in-degree of each node;
4. Add all the nodes with in-degree 0 into the queue;
5. Topological Sorting: while the queue is not empty, （1）Move the top element in the queue to the result array; （2）Update the in-degree of all its subsequent nodes, and put the nodes with in-degree 0 into the queue; （2）Update count;
6. Return the result array res.

Complexity Analysis

• Time complexity: $O(V+E)$ , (3) takes $O(E)$ time; (4) costs $O(V)$ time; 5(1) takes $O(1)$ time for each node, thus costing $O(V)$ time in total; 5(2) takes $O(E)$ time in total; Therefore, the total time complexity is $O(V+E)$;
• Space complexity: $O(V)$ , additionally define the variables: queue, degree , res , count, which taking up $O(V)$ space in total.

[songyy5517]

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // [a, b]: b -> a
        // Intuition: Topological Sorting
        // 1. Exception handling
        if (numCourses <= 1)
            return new int[numCourses];

        // 2. Define Variables  O(V)
        Queue<Integer> queue = new LinkedList();
        int[] degree = new int[numCourses];
        int[] res = new int[numCourses];

        // 3. Calculate the in-degree of each node  O(E)
        for (int i = 0; i < prerequisites.length; i++){
            degree[prerequisites[i][0]] ++;
        }

        // 4. Add the nodes with in-degree 0 into the queue  O(V)
        for (int i = 0; i < degree.length; i++){
            if (degree[i] == 0)
                queue.add(i);
        }

        // 5. Topological Sorting
        int count = 0;
        while (!queue.isEmpty()){
            // 5.1  Obtain the top element in the queue  O(V)
            res[count] = queue.remove();

            // 5.2  Update the in-degree of its subsequent nodes  O(E)
            for (int[] pair : prerequisites){
                if (pair[1] == res[count] && --degree[pair[0]] == 0){                 
                    queue.add(pair[0]);
                }

            }
            count ++;
        }

        // Check if all nodes are put into the array, otherwise there must be a cycle
        return count == numCourses ? res : new int[0];
    }
}

/*
Problem:
1. Determine whether cycled.
  - for: add index instead of degree
  - Use `count` to deternmine whether there is a cycle!

2. Complexity Analysis
  T:O(E) O(V)  O(V+E)
  S:O(V)
*/

[songyy5517]

2024/11/19