Course Schedule

The problem of Course Schedule on LeetCode is to determine if it is possible to finish all courses given the prerequisites. 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$.

One way to solve this problem is to use topological sorting, which orders the courses such that for every pair of courses $(a_i, b_i)$ where $b_i$ is a prerequisite of $a_i$, $b_i$ comes before $a_i$ in the ordering. If such an ordering exists, then it is possible to finish all courses. Otherwise, there is a cycle in the graph of courses and prerequisites, and it is impossible to finish all courses.

Here’s C++ implementation:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
  vector<int> inDegree(numCourses, 0);
  vector<vector<int>> graph(numCourses);

  // Build the graph and calculate in-degrees
  for (const vector<int> &prereq : prerequisites) {
    graph[prereq[1]].push_back(prereq[0]);
    inDegree[prereq[0]]++;
  }

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

  // Perform topological sorting
  while (!q.empty()) {
    int course = q.front();
    q.pop();
    numCourses--;

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

  return numCourses == 0;
}

int main() {
  int numCourses = 2;
  vector<vector<int>> prerequisites = {{1, 0}};

  if (canFinish(numCourses, prerequisites)) {
    cout << "You can finish all courses!" << endl;
  } else {
    cout << "You cannot finish all courses!" << endl;
  }

  return 0;
}

Here are the key steps in the solution:

1. Build the Graph: The first step is to build a directed graph to represent the courses and their prerequisites. In C++, this is done using a vector of vectors, where each course is a node, and each directed edge $(a, b)$ represents that course $a$ must be taken before course $b$.
2. Calculate In-degrees: For each course, calculate the in-degree, which is the number of prerequisites that must be taken before that course. This is done using an array or vector (inDegree) to store the in-degree of each course.
3. Initialize a Queue: Initialize a queue (q) to perform topological sorting. Add all courses with an in-degree of 0 to the queue because these are the courses that can be taken first.
4. Topological Sorting: Perform a BFS (Breadth-First Search) traversal of the graph using the queue. For each course taken from the queue, decrement the in-degrees of its neighbors (the courses that depend on it). If the in-degree of a neighbor becomes 0, add it to the queue because it can now be taken.
5. Check if All Courses Can Be Taken: After processing all courses, if the numCourses (initially representing the total number of courses) becomes 0, it means that all courses can be taken without violating any prerequisites, and the function returns true. Otherwise, it returns false, indicating that some courses cannot be completed due to circular dependencies.

This code has a time complexity of $O(V + E)$, where $V$ is the number of courses and $E$ is the number of prerequisites, and a space complexity of $O(V + E)$, since it uses an adjacency list and an in-degree array.