Course Schedule II medium

Problem Statement

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

Steps

1. Build the graph: Create an adjacency list to represent the course dependencies. Each course will be a node, and an edge from course b to course a indicates that b must be taken before a.

2. Calculate in-degrees: For each course, count its in-degree (the number of courses that must be taken before it).

3. Topological Sort (using Kahn's algorithm):

   • Initialize a queue with all courses having an in-degree of 0 (these courses have no prerequisites).
   • While the queue is not empty:
     • Dequeue a course.
     • Add it to the result list.
     • Decrement the in-degree of all its neighbors (courses that depend on it).
     • If a neighbor's in-degree becomes 0, add it to the queue.

4. Check for cycles: If the length of the result list is not equal to numCourses, it means there's a cycle in the graph, and it's impossible to finish all courses. Return an empty array in this case.

5. Return the result: Return the result list containing the topological ordering of courses.

Explanation

Kahn's algorithm is used for topological sorting. It efficiently handles directed acyclic graphs (DAGs). The algorithm starts with nodes that have no incoming edges (in-degree 0). These nodes can be processed first. After processing a node, its outgoing edges are removed, potentially reducing the in-degree of other nodes to 0, allowing them to be processed next. If a cycle exists, the queue will eventually become empty while not all nodes have been processed, indicating that a topological sort is impossible.

Code

#include <vector>
#include <queue>

std::vector<int> findOrder(int numCourses, const std::vector<std::vector<int>>& prerequisites) {
    std::vector<std::vector<int>> adj(numCourses);
    std::vector<int> inDegree(numCourses, 0);

    // Build the graph and calculate in-degrees
    for (const auto& pre : prerequisites) {
        adj[pre[1]].push_back(pre[0]);
        inDegree[pre[0]]++;
    }

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

    std::vector<int> result;
    while (!q.empty()) {
        int course = q.front();
        q.pop();
        result.push_back(course);

        for (int neighbor : adj[course]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    return result.size() == numCourses ? result : std::vector<int>();
}

Complexity

• Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). This is because we visit each vertex and edge once.
• Space Complexity: O(V + E) to store the adjacency list and in-degree array. The queue's size is at most V.