Course Schedule - Solution & Explanation

This problem can be translated into finding cycles in a directed graph. Each course is a node, and a prerequisite is a directed edge from one course to another. If there is a cycle in the graph, it means there is no way to complete all courses because a course depends on itself indirectly.

To detect cycles, we perform a Depth First Search (DFS). We maintain a visitation state for each node: 0 = unvisited, 1 = visiting (currently in stack), and 2 = visited. During DFS, if we encounter a node that is already in the visiting state, it implies the presence of a cycle.

We utilize a recursion stack to perform DFS on each node. When a node is being processed, it is marked as 'visiting'. If during the traversal we encounter a node that is already marked 'visiting', a cycle is present, and we return False. After processing, nodes are marked 'visited'. This implementation correctly detects cycles in the directed graph of course dependencies.

Kahn's Algorithm provides an alternative way to perform a topological sort and can be employed to detect cycles. The idea is to repeatedly remove nodes with no incoming edges (no prerequisites) and reduce the incoming edges of each node's neighbors. If we are left with unvisited nodes, these form a cycle.

Initially, we compute the in-degree (number of incoming edges) for each node. Nodes with zero in-degree are added to a queue. We dequeue a node, add it to the topological order, and reduce the in-degree of its neighbors.

In this Java implementation of Kahn's Algorithm, we initialize in-degrees for all courses. Nodes with zero in-degree are processed first. Processing involves adding them to an output list and decreasing the in-degree of their neighboring nodes. If a neighboring node's in-degree drops to zero, it becomes eligible for processing next.