Course Schedule 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 true if you can finish all courses. Otherwise, return false.

Example 1

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

Output: true

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2

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

Output: false

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Steps

1. Build the Graph: Create an adjacency list to represent the course dependencies. Each course is a node, and an edge from b to a indicates that course a depends on course b.

2. Indegree Calculation: Calculate the indegree (number of incoming edges) for each course. This represents the number of prerequisites a course has.

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

   • Initialize a queue with all courses that have an indegree of 0 (no prerequisites).
   • While the queue is not empty:
     • Dequeue a course.
     • Decrement the indegree of all its dependent courses.
     • If a dependent course's indegree becomes 0, add it to the queue.
   • If the number of visited courses (courses dequeued) equals numCourses, a topological sort was possible, and all courses can be completed. Otherwise, there's a cycle, and it's impossible to complete all courses.

Explanation

Kahn's algorithm is a classic way to perform topological sorting. It works by iteratively removing nodes with no incoming edges. If after processing all nodes, all nodes were processed, then it means there is no cycle and the topological sort is possible. Otherwise, there must be a cycle in the graph.

The existence of a cycle implies a circular dependency between courses, making it impossible to complete all courses.

Code

#include <vector>
#include <queue>

using namespace std;

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    // Create adjacency list (graph)
    vector<vector<int>> adj(numCourses);
    vector<int> indegree(numCourses, 0); // Initialize indegree for all courses

    // Build the graph and calculate indegrees
    for (const auto& pre : prerequisites) {
        adj[pre[1]].push_back(pre[0]); // pre[1] -> pre[0] (course pre[0] depends on pre[1])
        indegree[pre[0]]++;
    }

    // Find courses with no prerequisites (indegree 0)
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0; // Count of visited courses
    while (!q.empty()) {
        int course = q.front();
        q.pop();
        count++;

        // Update indegree of dependent courses
        for (int neighbor : adj[course]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    return count == numCourses; // If all courses were visited, there's no cycle
}

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 the indegree array. The queue's space usage is at most O(V) in the worst case.