# LeetCode 207: Course Schedule

## Problem Restatement

We are given:

- `numCourses`
- a list of prerequisite pairs

Each pair:

```python
[a, b]
```

means:

```text
to take course a, you must first complete course b
```

We need to determine whether it is possible to finish all courses.

The official statement says: there are `numCourses` courses labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you must take course `bi` first if you want to take course `ai`. Return `true` if you can finish all courses. Otherwise return `false`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `numCourses` and prerequisite pairs |
| Output | `True` if all courses can be completed, otherwise `False` |
| Graph meaning | Directed edge `b -> a` |
| Main challenge | Detect cycles |

Example function shape:

```python
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    ...
```

## Examples

Example 1:

```python
numCourses = 2
prerequisites = [[1,0]]
```

Meaning:

```text
0 -> 1
```

Take course `0` first, then course `1`.

Possible ordering:

```text
0, 1
```

Answer:

```python
True
```

Example 2:

```python
numCourses = 2
prerequisites = [[1,0],[0,1]]
```

Graph:

```text
0 -> 1
1 -> 0
```

This creates a cycle.

To take `0`, we need `1`.

To take `1`, we need `0`.

Impossible.

Answer:

```python
False
```

## Understanding the Graph

This problem is a directed graph problem.

Each course is a node.

Each prerequisite relation is a directed edge.

Example:

```python
[1, 0]
```

means:

```text
0 -> 1
```

because course `0` must happen before course `1`.

The important observation:

- If the graph contains a cycle, the courses cannot be completed.
- If the graph is acyclic, the courses can be completed.

So the real problem becomes:

```text
Does the directed graph contain a cycle?
```

## Key Insight

A valid course ordering exists exactly when the graph is a Directed Acyclic Graph (DAG).

So we only need cycle detection.

There are two classic solutions:

| Method | Idea |
|---|---|
| DFS | Detect back edges during traversal |
| BFS Topological Sort | Repeatedly remove nodes with indegree `0` |

We will start with BFS topological sorting because it is often easier to visualize.

## Topological Sorting Idea

A course with indegree `0` has no remaining prerequisites.

So we can safely take it first.

After taking it:

- remove its outgoing edges
- reduce indegrees of dependent courses

Repeat until no more courses are available.

If we process every course, the graph had no cycle.

If some courses remain locked forever, there must be a cycle.

## Algorithm (BFS / Kahn's Algorithm)

1. Build the graph.
2. Compute indegree of every course.
3. Push every course with indegree `0` into a queue.
4. Repeatedly:
   - pop a course
   - count it as completed
   - reduce indegree of neighbors
   - if a neighbor becomes `0`, push it into the queue
5. If completed course count equals `numCourses`, return `True`.
6. Otherwise return `False`.

## Walkthrough

Use:

```python
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
```

Graph:

```text
0 -> 1
0 -> 2
1 -> 3
2 -> 3
```

Initial indegrees:

| Course | Indegree |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |

Queue starts with:

```text
[0]
```

Process `0`.

Reduce indegrees:

| Course | New Indegree |
|---|---|
| 1 | 0 |
| 2 | 0 |

Push:

```text
[1, 2]
```

Process `1`.

Reduce indegree of `3`:

```text
2 -> 1
```

Process `2`.

Reduce indegree of `3`:

```text
1 -> 0
```

Push `3`.

Eventually all four courses are processed.

Answer:

```python
True
```

## Why Cycles Break the Process

Suppose:

```python
prerequisites = [[1,0],[0,1]]
```

Indegrees:

| Course | Indegree |
|---|---|
| 0 | 1 |
| 1 | 1 |

No course has indegree `0`.

The queue starts empty.

We cannot begin.

That means the graph contains a cycle.

## Correctness

The algorithm repeatedly selects courses with indegree `0`.

A course with indegree `0` has no unmet prerequisites, so it is safe to complete.

When the algorithm removes such a course, it also removes all outgoing edges from that course by decrementing neighbor indegrees. This correctly models completing the prerequisite.

If the graph is acyclic, there is always at least one node with indegree `0`. Therefore the algorithm continues removing courses until all courses are processed.

If the graph contains a cycle, every node in the cycle always has at least one incoming edge from another node in the cycle. No node in the cycle can ever reach indegree `0`.

Therefore the queue eventually becomes empty before all courses are processed.

So:

- processing all courses means the graph is acyclic
- failing to process all courses means the graph contains a cycle

Thus the algorithm correctly determines whether all courses can be completed.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(V + E)` | Each node and edge is processed once |
| Space | `O(V + E)` | Graph, indegree array, and queue |

Where:

- `V = numCourses`
- `E = number of prerequisite pairs`

## BFS Topological Sort Implementation

```python
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque()

        for course in range(numCourses):
            if indegree[course] == 0:
                queue.append(course)

        completed = 0

        while queue:
            current = queue.popleft()
            completed += 1

            for neighbor in graph[current]:
                indegree[neighbor] -= 1

                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        return completed == numCourses
```

## Code Explanation

Build adjacency list:

```python
graph = [[] for _ in range(numCourses)]
```

Build indegree array:

```python
indegree = [0] * numCourses
```

For every prerequisite:

```python
graph[prereq].append(course)
indegree[course] += 1
```

Push all courses with no prerequisites:

```python
if indegree[course] == 0:
    queue.append(course)
```

Process courses:

```python
current = queue.popleft()
```

Reduce indegrees of dependent courses:

```python
indegree[neighbor] -= 1
```

If a course becomes available:

```python
if indegree[neighbor] == 0:
    queue.append(neighbor)
```

Finally:

```python
return completed == numCourses
```

If every course was processed, there was no cycle.

## DFS Cycle Detection Solution

We can also detect cycles directly using DFS.

Each node has three states:

| State | Meaning |
|---|---|
| `0` | Unvisited |
| `1` | Currently visiting |
| `2` | Fully processed |

If DFS reaches a node already marked `1`, we found a cycle.

## DFS Implementation

```python
class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]

        for course, prereq in prerequisites:
            graph[prereq].append(course)

        state = [0] * numCourses

        def dfs(node):
            if state[node] == 1:
                return False

            if state[node] == 2:
                return True

            state[node] = 1

            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False

            state[node] = 2

            return True

        for course in range(numCourses):
            if not dfs(course):
                return False

        return True
```

## DFS Explanation

When entering a node:

```python
state[node] = 1
```

This means the node is currently inside the recursion stack.

If DFS reaches another node already marked `1`, then we returned to an unfinished ancestor, which forms a cycle.

After fully processing a node:

```python
state[node] = 2
```

This means the node is safe and fully explored.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.canFinish(2, [[1,0]]) is True
    assert s.canFinish(2, [[1,0],[0,1]]) is False
    assert s.canFinish(4, [[1,0],[2,0],[3,1],[3,2]]) is True
    assert s.canFinish(1, []) is True
    assert s.canFinish(3, [[1,0],[2,1],[0,2]]) is False

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[[1,0]]` | Simple valid dependency |
| `[[1,0],[0,1]]` | Direct cycle |
| Larger DAG | Multi-layer ordering |
| Empty prerequisites | No dependencies |
| Three-node cycle | Indirect cycle detection |