Course Schedule

Problem Statement

In this challenge, you are tasked with determining whether all the courses from a list can be successfully completed given certain prerequisite constraints. Each course is uniquely identified with an integer label ranging from 0 to numCourses - 1. The prerequisites are specified in an array where each element is a pair [ai, bi]. This pair means that course ai can only be taken after course bi has been completed. Your goal is to return true if it is feasible to take all courses in compliance with these prerequisites. If there's any circular dependency or if it's impossible to meet the prerequisites to complete all courses, you should return false.

Examples

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.

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Approach and Intuition

To solve this problem, understanding the relationship between courses can be visualized as a graph problem where:

• Each course can be considered as a node.
• A directed edge from node bi to node ai is added if there's a prerequisite that course ai requires completion of course bi first.

The essence of this problem boils down to detecting a cycle in the directed graph:

1. If there is a cycle, it means there is at least one course that requires itself indirectly to be completed beforehand, making it impossible to finish such a course. Hence, the function should return false.
2. Conversely, if no cycle exists, all courses can be taken respecting the given order in the prerequisites, and the function should return true.

Common algorithms to detect cycles in a directed graph include:

• Depth-First Search (DFS) which can be modified to keep track of visited nodes and the path currently being explored.
• Kahn's Algorithm, which uses the idea of topological sorting. It starts with nodes with no incoming edges (no prerequisites) and processes them, effectively reducing the in-degree of its adjacent nodes. Nodes which then have zero in-degree are subsequently added to the processing list. If all nodes are processed without issues, no cycle exists.

Using these insights and checking the relationships specified in the examples:

• Example 1: There is a simple linear dependency: Course 0 must be completed before Course 1. There's no cycle here, making it possible to complete these courses.

• Example 2: There is a direct cycle between Courses 0 and 1, where each is a prerequisite for the other. This situation makes it impossible to complete the courses, as they depend on the completion of each other.

These examples illustrate how the presence or absence of cycles affects the possibility of completing all the courses. Each scenario under the constraints should be processed with these considerations to determine the outcome efficiently.

Solutions

class Solution {
public:
    bool cycleDetection(int course, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& recursionStack) {
        if (recursionStack[course]) {
            return true;
        }
        if (visited[course]) {
            return false;
        }
    
        visited[course] = true;
        recursionStack[course] = true;
        for (int neighbor : graph[course]) {
            if (cycleDetection(neighbor, graph, visited, recursionStack)) {
                return true;
            }
        }
    
        recursionStack[course] = false;
        return false;
    }
    
    bool canCompleteCourses(int totalCourses, vector<vector<int>>& dependencies) {
        vector<vector<int>> graph(totalCourses);
        for (auto dependency : dependencies) {
            graph[dependency[1]].push_back(dependency[0]);
        }
    
        vector<bool> visited(totalCourses), recursionStack(totalCourses);
        for (int i = 0; i < totalCourses; i++) {
            if (cycleDetection(i, graph, visited, recursionStack)) {
                return false;
            }
        }
        return true;
    }
};