Course Schedule

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;
    }
};

The provided C++ solution addresses the problem of determining whether it is possible to complete all courses given a list of prerequisites, which form a directed graph. Here is a breakdown of the implementation strategy:

• Graph Representation: The courses and their dependencies are represented using an adjacency list, where each course is a key node and its list of subsequent courses forms the connected nodes.
• Cycle Detection: Central to solving the problem is detecting cycles in the course dependency graph. If a cycle exists, it is not possible to complete all the courses, as it would create a circular dependency.
• Depth-First Search (DFS) Algorithm: The cycleDetection function utilizes a DFS approach to explore each course and its dependencies. It tracks nodes in two ways: nodes that have been visited (visited vector) and nodes that are currently in the recursion stack (recursionStack vector).
  • If a node is encountered again in the recursion stack, a cycle is detected and the function returns true for a cycle.
  • If a node was visited but not currently in the recursion stack, it is skipped as its subgraph does not contain a cycle.
  • Each course and its dependencies are processed, marking them as visited and adding to the recursion stack as the search goes deeper.
• Check All Courses: The canCompleteCourses function sets up the graph and also initializes the visited and recursion stack arrays. It iterates through all the courses and uses the cycleDetection function to check for cycles originating from each course.
• Decision Point: Depending on the presence of a cycle detected through the cycleDetection, the canCompleteCourses function will return false (if any cycle is detected, implying not all courses can be completed) or true (if no cycles are detected, implying all courses can be completed).

This approach ensures that the program efficiently identifies the feasibility of completing the courses based on the given prerequisites by effectively utilizing graph traversal and cycle detection techniques in a DFS framework.

class Solution {
    public boolean explore(int vertex, List<List<Integer>> graph, boolean[] visited, boolean[] recursionStack) {
        if (recursionStack[vertex]) {
            return true;
        }
        if (visited[vertex]) {
            return false;
        }
        visited[vertex] = true;
        recursionStack[vertex] = true;
        for (int neighbor : graph.get(vertex)) {
            if (explore(neighbor, graph, visited, recursionStack)) {
                return true;
            }
        }
        recursionStack[vertex] = false;
        return false;
    }

    public boolean isPossibleToFinish(int totalCourses, int[][] dependencies) {
        List<List<Integer>> graph = new ArrayList<>(totalCourses);
        for (int i = 0; i < totalCourses; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] pair : dependencies) {
            graph.get(pair[1]).add(pair[0]);
        }

        boolean[] visited = new boolean[totalCourses];
        boolean[] recursionStack = new boolean[totalCourses];
        for (int i = 0; i < totalCourses; i++) {
            if (explore(i, graph, visited, recursionStack)) {
                return false;
            }
        }
        return true;
    }
}

The provided Java solution addresses the problem of determining whether it is possible to complete all courses given a list of course dependencies, which can be visualized as a directed graph. This graph problem is typically known as detecting a cycle in a directed graph.

• Initialize a method explore to perform a Depth First Search (DFS) to detect cycles. If a cycle is detected at any node (vertex), it indicates that finishing all courses is not possible.

• Use two boolean arrays, visited and recursionStack. visited tracks nodes that have been completely processed, while recursionStack tracks nodes currently in the recursion stack (i.e., nodes in the current path of DFS).

• For each vertex:

  • If it's already in the recursion stack (recursionStack[vertex] is true), a cycle is detected.
  • If it's already visited and processed (visited[vertex] is true), skip further exploration.

• Recursively visit all the neighbors of the current vertex. If any recursive call returns true, propagate that true back up the call stack, indicating a cycle.

• Before backtracking, mark the current vertex as not in the recursion stack (recursionStack[vertex] = false).

• In the isPossibleToFinish method:

  • Construct the adjacency list graph for the courses based on given dependencies.
  • For each course, represented by index i, if it has not been visited, initiate the DFS from that vertex. If explore returns true for any vertex, a cycle exists, making it impossible to complete all courses.

If the algorithm determines there's no cycle in the graph, it returns true, confirming that it's possible to finish all courses by following some sequence allowed by the dependencies. If a cycle exists (detected by explore method returning true), it returns false.

class GraphAnalyzer:
    def explore(self, vertex, graph, visited, recursionStack):
        if recursionStack[vertex]:
            return True
        if visited[vertex]:
            return False
        visited[vertex] = True
        recursionStack[vertex] = True
        for adjacent in graph[vertex]:
            if self.explore(adjacent, graph, visited, recursionStack):
                return True
        recursionStack[vertex] = False
        return False

    def canCompleteCourses(self, totalCourses: int, dependencies: List[List[int]]) -> bool:
        edges = [[] for _ in range(totalCourses)]
        for dep in dependencies:
            edges[dep[1]].append(dep[0])

        visited = [False] * totalCourses
        recursionStack = [False] * totalCourses
        for course in range(totalCourses):
            if self.explore(course, edges, visited, recursionStack):
                return False
        return True

The solution provided defines a Python class, GraphAnalyzer, that assists in determining if a set of courses can all be completed given their dependencies. This is analogous to detecting a cycle in a directed graph, where each course represents a node, and dependencies represent directed edges.

The class contains two main methods:

• explore(self, vertex, graph, visited, recursionStack): A helper method used in detecting a cycle in the graph. It employs depth-first search (DFS):

  • Checks if the current vertex is already in the recursion stack (indicating a cycle) and returns True if found.
  • Otherwise, marks the vertex as visited.
  • Recursively explores all adjacent vertices (dependencies), and if a cycle is detected in any adjacent exploration, it bubbles up the result.
  • Once all adjacents are visited without finding a cycle, it removes the vertex from the recursion stack and returns False.

• canCompleteCourses(self, totalCourses: int, dependencies: List[List[int]]) -> bool: Determines if completing all courses is feasible:

  • Initializes a list of lists, edges, to represent the graph, where each index indicates a course and its list contains the courses that depend on it.
  • An iteration over totalCourses employs the explore method to ensure no dependency cycles exist which would prevent course completion.
  • The method finally returns True if all courses can be completed (i.e., no cycles were found).

This implementation is effective for solving the problem of course scheduling by converting it into a cycle detection problem in a directed graph.