Course Schedule I and II | Pre-requisite Tasks | Topological Sort

This comprehensive study note explores Course Schedule I and II (LeetCode 207 and 210), breaking down how prerequisite dependency management maps directly to Topological Sorting and Cycle Detection in Directed Graphs.

1. Why Do We Need This? (Problem Statement & Status Quo)

In real-world systems, tasks, courses, or compilation steps often have strict ordering constraints.

• The Core Problem: You are given a total of $N$ tasks labeled from $0$ to $N-1$ and a list of prerequisite pairs. For instance, a pair [0, 1] means: "To perform task 0, you must first complete task 1."
• Course Schedule I (Detect Feasibility): Determine whether it is possible to finish all tasks (i.e., whether a valid execution order exists). Return true or false (or yes / no).
• Course Schedule II (Find Ordering): Return the exact linear ordering of tasks you should take to finish all courses. If it is impossible (due to circular dependencies), return an empty array.

2. Core Mental Model: The Prerequisite Chain

Real-Life Analogy: Getting Dressed

Think about getting dressed in the morning. Certain items depend on others:

• You must put on your socks before your shoes.
• You must put on your shirt before your jacket.

If someone gives you a rulebook where shoe-wearing precedes socks, but sock-wearing also requires shoes, you are stuck in an impossible loop. Topological sorting formalizes this dependency graph.

Mapping Prerequisites to Directed Edges

When the problem states: "To perform task 0, you must first perform task 1", we can express this dependency as a directed edge:

This means Task 1 must precede Task 0 in our final execution sequence.

3. Naive Approach vs. Topological Sort

4. Step-by-Step Evolution: Feasibility to Ordering

When is a Schedule Impossible?

A schedule is impossible if and only if the directed graph contains a cycle. Consider this cyclic dependency:

• Task 1 must be done before Task 2.
• Task 2 must be done before Task 4.
• Task 4 must be done before Task 1 (contradiction!).

Because a cycle prevents any single task in the loop from having a zero in-degree (no prerequisites remaining), Kahn's Algorithm for Topological Sort will fail to visit all vertices.

5. Complete Flow Walkthrough (Kahn's Algorithm BFS Approach)

Let's trace how Kahn's Algorithm resolves Course Schedule problems:

1. Build Adjacency List & In-Degree Array:
   • Compute indegree[i] for every node (count of incoming edges).
2. Initialize Queue:
   • Push all nodes with indegree == 0 into a BFS queue (these have zero prerequisites and can be done immediately).
3. Process Queue:
   • Pop a node from the queue, add it to the topological ordering result list.
   • For each neighbor of the popped node, decrement its indegree by 1.
   • If a neighbor's indegree drops to 0, push it into the queue.
4. Validation Check:
   • If the size of the result list equals the total number of tasks $V$, a valid schedule exists. Otherwise, a cycle exists.

6. Implementation Code (C++ & Java Equivalent Logic)

Course Schedule I: Return Boolean (isPossible)

#include <vector>
#include <queue>
using namespace std;

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses);
    vector<int> indegree(numCourses, 0);

    // Build graph (Note: prerequisite format [0, 1] means 1 -> 0)
    for (auto& pre : prerequisites) {
        int course = pre[0];
        int prereq = pre[1];
        adj[prereq].push_back(course);
        indegree[course]++;
    }

    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        count++;

        for (auto neighbor : adj[node]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    return count == numCourses;
}

Course Schedule II: Return Exact Ordering Array

#include <vector>
#include <queue>
using namespace std;

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses);
    vector<int> indegree(numCourses, 0);

    for (auto& pre : prerequisites) {
        // Course Schedule II reverses pair format depending on problem statement variant,
        // here we map pre[1] -> pre[0] (prerequisite to target course)
        int course = pre[0];
        int prereq = pre[1];
        adj[prereq].push_back(course);
        indegree[course]++;
    }

    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topoOrder;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        topoOrder.push_back(node);

        for (auto neighbor : adj[node]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // If topoOrder contains all courses, return it; otherwise empty array (cycle detected)
    if (topoOrder.size() == numCourses) {
        return topoOrder;
    }
    return {};
}

7. Real-World Practical Pitfalls & Edge Cases

• Reversed Prerequisite Pairs: Different platforms or problem versions format pairs differently ([0, 1] meaning 1 before 0 vs 0 before 1). Always carefully verify whether pair[0] depends on pair[1] or vice-versa.
• Disconnected Graphs: The prerequisite graph may consist of multiple disjoint components. Initializing the BFS queue with all nodes having indegree == 0 correctly handles multiple independent component roots.
• Self-Loops & Parallel Edges: Input data might occasionally contain self-dependencies ([1, 1]) or duplicate prerequisite listings. Ensure your graph builder handles in-degrees cleanly without double-decrementing.

8. Summary and Key Takeaways

• Topological Sort Definition: A linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge $u \to v$, vertex $u$ comes before vertex $v$.
• Cycle Detection equivalence: Topological sorting is only possible if and only if the graph has no cycles (DAG).
• Kahn's Algorithm (BFS): Uses in-degree tracking and a zero-in-degree queue to cleanly traverse and sequence dependencies in $O(V + E)$ time.
• Course Schedule I: Returns true if all tasks can be completed (no cycles), false otherwise.
• Course Schedule II: Returns the ordered sequence of tasks, or an empty array [] if circular dependencies make execution impossible.
• Intuition Trigger: Whenever a problem mentions "do X before Y" or "prerequisite tasks", immediately map it to a Directed Graph with Topological Sort.