Course Schedule - Python Solution

1. Introduction

The "Course Schedule" problem is a fundamental challenge in graph algorithms and topological sorting, often encountered in systems design and educational planning. The problem involves determining if a set of courses with prerequisites can be completed without conflicts. This problem tests one's ability to apply graph theory concepts and detect cycles in directed graphs.

Problem

Given a total of numCourses courses labeled from 0 to numCourses - 1, and an array prerequisites where prerequisites[i] = [ai, bi] indicates that course bi must be taken first to take course ai, the task is to return true if you can finish all courses, otherwise return false.

2. Solution Steps

1. Create a graph to represent the courses and their prerequisites.

2. Initialize an adjacency list and a degree array to keep track of the number of prerequisites for each course.

3. Populate the adjacency list and degree array based on the prerequisites.

4. Use a queue to perform a topological sort.

5. Enqueue all courses with no prerequisites (degree 0).

6. Process each course in the queue, reducing the degree of its dependent courses.

7. If a dependent course's degree becomes 0, enqueue it.

8. If all courses are processed (queue is empty), return true. If some courses are left with non-zero degrees, return false.

3. Code Program

from collections import deque

def canFinish(numCourses, prerequisites):
    adj_list = [[] for _ in range(numCourses)]
    degree = [0] * numCourses

    # Create the adjacency list and degree array
    for dest, src in prerequisites:
        adj_list[src].append(dest)
        degree[dest] += 1

    # Queue for courses with no prerequisites
    queue = deque([i for i in range(numCourses) if degree[i] == 0])

    while queue:
        course = queue.popleft()
        for next_course in adj_list[course]:
            degree[next_course] -= 1
            if degree[next_course] == 0:
                queue.append(next_course)

    return all(d == 0 for d in degree)

# Example Usage
print(canFinish(2, [[1,0]]))
print(canFinish(2, [[1,0], [0,1]]))

Output:

True
False

Explanation:

1. Graph Representation: The courses and prerequisites are represented as a directed graph.

2. Topological Sorting: The solution uses a topological sort algorithm to process the courses.

3. Degree Array: The degree array keeps track of how many prerequisites each course has.

4. Queue Processing: Courses with no prerequisites are processed first, reducing the degrees of dependent courses.

5. Cycle Detection: If a cycle exists (i.e., some courses still have prerequisites remaining), it's impossible to complete all courses.

6. Completion Check: If all courses' degrees are reduced to 0, it means all courses can be completed.