# 1. Introduction

This blog post explores the "Course Schedule" problem, an essential problem in graph theory and topological sorting. The challenge is to determine if it's possible to finish all courses given certain prerequisites. This problem is a typical example of detecting cycles in a directed graph, a key concept in computer science and scheduling tasks.

## Problem

In a scenario with *numCourses* courses labeled from 0 to *numCourses - 1*, and a list of prerequisites represented as a pair *[ai, bi]* (where you must take course *bi* before course *ai*), the task is to determine if it's possible to finish all courses. If it is possible, return *true*, otherwise return *false*.

# 2. Solution Steps

1. Create a graph representing the courses and their prerequisites using an adjacency list.

2. Use depth-first search (DFS) to detect cycles in the graph:

a. Keep track of visited nodes and nodes in the current DFS path.

b. If a node is encountered that is already in the current DFS path, a cycle is detected.

3. Return *true* if no cycles are found, meaning all courses can be finished; otherwise, return *false*.

# 3. Code Program

```
import java.util.ArrayList;
import java.util.List;
public class CourseSchedule {
public static void main(String[] args) {
int numCourses = 2;
int[][] prerequisites = {{1, 0}};
System.out.println(canFinish(numCourses, prerequisites)); // Test the function
}
// Function to check if all courses can be finished
public static boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
graph.get(prerequisite[1]).add(prerequisite[0]);
}
boolean[] visited = new boolean[numCourses];
boolean[] recStack = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!visited[i]) {
if (isCyclic(graph, i, visited, recStack)) {
return false;
}
}
}
return true;
}
// Helper function to detect a cycle in the graph
private static boolean isCyclic(List<List<Integer>> graph, int node, boolean[] visited, boolean[] recStack) {
if (recStack[node]) return true;
if (visited[node]) return false;
visited[node] = true;
recStack[node] = true;
for (int neighbor : graph.get(node)) {
if (isCyclic(graph, neighbor, visited, recStack)) {
return true;
}
}
recStack[node] = false;
return false;
}
}
```

### Output:

true

### Explanation:

1. *canFinish*: This function builds a graph representation of courses and their prerequisites. It then iterates through each course and uses the *isCyclic* helper function to check for cycles in the graph.

2. The graph is represented as an adjacency list, where each index is a course and the list at each index contains the courses that depend on it.

3. *isCyclic*: This function performs a DFS on the graph. It uses two boolean arrays, *visited* and *recStack*, to keep track of visited nodes and nodes currently in the recursion stack, respectively.

4. If any node in the current DFS path is encountered again, a cycle is detected, indicating that it's impossible to complete all courses (returns *false*).

5. If no cycles are detected, the function returns *true*, indicating that it's possible to complete all courses.

6. This approach effectively checks for course dependencies and ensures that no circular prerequisites exist, which would make completing all courses impossible.

## Comments

## Post a Comment