Course Schedule

You are given a total number of courses (n) and a list of prerequisites represented as pairs of course numbers. The prerequisites indicate that to take course prerequisites[i][0], you must first complete course prerequisites[i][1]. It is guaranteed that a valid ordering of courses exists.

You need to determine if it is possible to complete all courses by taking the courses in a valid order (no circular dependencies).

Example:

Input:

n = 4
prerequisites = [[1, 0], [2, 1], [3, 2]]

Explanation: To take course 1, you need to take course 0 first. To take course 2, you need to take course 1 first, and so on. A valid ordering would be: 0 -> 1 -> 2 -> 3

Output:

true

Input:

n = 2
prerequisites = [[1, 0], [0, 1]]

Explanation: To take course 1, you need to take course 0 first, and to take course 0, you need to take course 1 first. There is a circular dependency, and it is not possible to complete all courses.

Output:

false

Time Complexity:

The time complexity of the solution is O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges).

Space Complexity:

The space complexity of the solution is O(V + E) due to the adjacency list representation of the graph.

Course Schedule C++ Solution:

#include <vector>
#include <queue>

using namespace std;

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses); // Adjacency list representation of the graph
    vector<int> inDegree(numCourses, 0); // In-degree of each course

    // Create the graph and calculate the in-degree of each course
    for (const auto& edge : prerequisites) {
        graph[edge[1]].push_back(edge[0]); // Add directed edge from edge[1] to edge[0]
        inDegree[edge[0]]++; // Increment the in-degree of edge[0]
    }

    queue<int> q;

    // Add all courses with in-degree 0 to the queue
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    int numTakenCourses = 0;

    while (!q.empty()) {
        int currentCourse = q.front();
        q.pop();
        numTakenCourses++;

        // Process all dependent courses (outgoing edges)
        for (int dependentCourse : graph[currentCourse]) {
            inDegree[dependentCourse]--; // Reduce the in-degree of the dependent course

            // If the dependent course now has in-degree 0, add it to the queue
            if (inDegree[dependentCourse] == 0) {
                q.push(dependentCourse);
            }
        }
    }

    // If the number of taken courses is equal to the total number of courses, return true
    // Otherwise, there must be a cycle in the graph, so return false
    return numTakenCourses == numCourses;
}

Explanation of Code:

1. We create an adjacency list representation of the graph using the graph vector. Each index i in the graph vector corresponds to a course, and the elements of graph[i] are the courses that depend on course i.
2. We create a vector inDegree to keep track of the in-degree of each course. The in-degree of a course is the number of prerequisite courses it has.
3. We populate the graph and calculate the in-degree for each course based on the given prerequisites.
4. We use a queue to perform a Breadth-First Search (BFS) on the graph. Initially, we add all courses with in-degree 0 (no prerequisites) to the queue.
5. In each iteration of the BFS, we take a course from the front of the queue, increment the count of taken courses, and process its dependent courses (outgoing edges).
6. For each dependent course, we reduce its in-degree since one of its prerequisites (the current course) is taken. If the in-degree becomes 0, we add the dependent course to the queue.
7. We repeat the process until the queue is empty.
8. Finally, if the number of taken courses is equal to the total number of courses, it means all courses can be completed in a valid order, so we return true. Otherwise, there must be a cycle, and it is not possible to complete all courses, so we return false.