Course Schedule II

Link

Description

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

• 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]

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= a_i, b_i < numCourses
• a_i != b_i
• All the pairs [a_i, b_i] are distinct.

Solution

Way 1

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses);
        vector<int> inDegree(numCourses);

        for (const auto& info : prerequisites) {
            edges[info[1]].push_back(info[0]);
            inDegree[info[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0)
                q.push(i);
        }

        vector<int> res;
        while (!q.empty()) {
            int current = q.front();
            q.pop();

            res.push_back(current);
            for (int v : edges[current]) {
                if (--inDegree[v] == 0)
                    q.push(v);
            }
        }

        if (res.size() < numCourses) return {};
        return res;
    }
};

This problem is a classic example of using topological sort in a directed graph, where courses are represented as nodes and prerequisites as directed edges. The algorithm aims to find a linear ordering of the vertices such that for every directed edge \(U,V\) from vertex \(U\) to vertex \(V\), \(U\) comes before \(V\) in the ordering.

Algorithm Steps:

1. Representation of Graph: The graph is represented using an adjacency list (edges), where edges[i] contains a list of courses that can be taken after completing course i. Additionally, an inDegree array is used to keep track of the number of prerequisites (incoming edges) for each course.

2. Building the Graph: The prerequisites list is iterated to build the graph and update the in-degree of each node. For each pair [a, b] in prerequisites, an edge from b to a is added to the graph, indicating that b is a prerequisite of a. Consequently, the in-degree of a is incremented.

3. Initializing the Queue: A queue is used to keep track of all courses (nodes) that have no prerequisites (in-degree of 0). These courses are safe to take first, as they do not depend on the completion of any other courses.

4. Processing the Queue: While the queue is not empty, the algorithm repeatedly removes a course from the queue and adds it to the result list (res). It then decreases the in-degree of all its dependent courses by 1, because taking the current course satisfies one of their prerequisites. If any of these courses now have no remaining prerequisites (in-degree becomes 0), they are added to the queue.

5. Checking for a Possible Order: After processing all courses, if the size of the result list is less than numCourses, it means not all courses can be completed (due to a cycle or unsatisfiable prerequisites), and an empty array is returned. Otherwise, the list res provides a valid order in which all courses can be finished.

Complexity Analysis:

• Time Complexity: \(O(V + E)\), where \(V\) is the number of courses (numCourses), and \(E\) is the number of prerequisites. Building the graph requires \(O(E)\) time, and each node and edge is processed exactly once in the topological sort.
• Space Complexity Analysis: \(O(V + E)\). The adjacency list (edges) stores all edges, and the in-degree array, queue, and result list collectively store information for all vertices. Therefore, the space complexity is proportional to the total number of courses and prerequisites.

Pseudocode:

function topologicalSort(numCourses, prerequisites):
    Initialize an empty list (or array) `edges` of size numCourses to represent the adjacency list
    Initialize an array `inDegree` of size numCourses to keep track of each node's in-degree (set all to 0)

    # Build the graph
    for each pair [course, prereq] in prerequisites:
        add course to edges[prereq]
        increment inDegree[course]

    Initialize an empty queue `q`

    # Find all nodes with in-degree 0
    for each course from 0 to numCourses-1:
        if inDegree[course] == 0:
            enqueue course into `q`

    Initialize an empty list `res` to store the order of courses

    # Process nodes with in-degree 0
    while q is not empty:
        current = dequeue from `q`
        add current to `res`

        # Decrease the in-degree of neighboring nodes
        for each neighbor in edges[current]:
            decrement inDegree[neighbor]
            if inDegree[neighbor] == 0:
                enqueue neighbor into `q`

    # Check if a valid ordering is found
    if length of `res` is equal to numCourses:
        return `res`
    else:
        return an empty list (indicating no valid ordering exists)

Way 2

class Solution {
private:
    static const int N = 400010;
    int h[N], e[N], ne[N], idx;
    int inDegree[N];
    int que[N], hh, tt;

    void addEdge(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }

    /*
    Initializes the queue with courses that have no prerequisites.
    Iterates over the queue, processing each course, and adding it to the result list res.
    For each course processed, it iterates through its adjacency list (outgoing edges) 
        to decrement the in-degree of connected courses. 
        If a course's in-degree drops to 0, it is added to the queue.
    Returns true if all courses are processed (indicating a valid topological order exists), otherwise false.
    */
    bool topologicalSort(int numCourses, vector<int>& res) {
        for (int i = 0; i < numCourses; i++) {
            if (!inDegree[i])
                que[++tt] = i;
        }

        while (hh <= tt) {
            int current = que[hh++];
            res.push_back(current);

            for (int i = h[current]; i != -1; i = ne[i]) {
                int v = e[i];
                if (--inDegree[v] == 0)
                    que[++tt] = v;
            }
        }

        return res.size() == numCourses;
    }

public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        memset(h, -1, sizeof(h));
        memset(inDegree, 0, sizeof(inDegree));
        memset(que, 0, sizeof(que));
        idx = 0, hh = 0, tt = -1;

        for (const auto& info : prerequisites) {
            addEdge(info[1], info[0]);
            inDegree[info[0]]++;
        }

        vector<int> res;
        if (topologicalSort(numCourses, res)) {
            return res;
        }
        return {};
    }
};

Class Members:

• h, e, ne: Arrays used to represent the graph.
• idx: A counter used to keep track of the number of edges added to the graph.
• inDegree: Array to track the number of incoming edges (prerequisites) for each course.
• que: Array used as a queue to store courses with no current prerequisites.
• hh, tt: Head and tail pointers for the queue represented by que.

Graph Representation:

This solution uses a more space-efficient method for representing graphs, especially sparse graphs, known as the adjacency list using arrays:

• h[a] stores the head of the linked list for vertex a, pointing to its first outgoing edge.
• e[i] represents the endpoint (or target node) of the i-th edge.
• ne[i] points to the next edge in the list originating from the same vertex as the i-th edge, creating a chain of all outgoing edges from a vertex.
• This representation is efficient in terms of memory and is particularly useful in graph algorithms where edge lookups and additions are frequent.