Course Schedule II

How it works

We want an order of courses such that every course appears after its prerequisites. This approach mixes Topological Sorting with DFS-style traversal.

The idea is:

• Start from courses that have no prerequisites (indegree = 0)
• Once we take a course, we "remove" it by decreasing the indegree of courses that depend on it
• When a dependent course's indegree becomes 0, it is now safe to take, so we continue DFS from it

If we can visit all courses this way, a valid order exists. If not, a cycle is present, making it impossible.

Steps

1. Build a directed graph from prerequisites and compute indegree for each course.
2. For every course with indegree = 0, start a DFS.
3. In DFS:
   • Add the current course to the result.
   • Decrease indegree of its neighbors.
   • If any neighbor's indegree becomes 0, recursively DFS on it.
4. After traversal:
   • If result contains all courses, return it.
   • Otherwise, return an empty list (cycle detected).

Complexity

• Time complexity: O(V + E)
• Space complexity: O(V + E)

Where V is the number of courses and E is the number of prerequisites.

Things to watch for

Confusing Cycle Detection with Visited Tracking

In DFS-based topological sort, you need two separate tracking mechanisms: one for nodes currently in the DFS path (for cycle detection) and one for fully processed nodes. Using only one set leads to either false cycle detection or infinite loops.

Building the Graph in the Wrong Direction

The prerequisite pair [a, b] means "to take course a, you must first take course b". Building edges in the wrong direction results in an incorrect topological order.

Forgetting to Handle Disconnected Courses

Courses with no prerequisites and no dependents still need to be included in the output. Forgetting to iterate over all courses means some valid courses might be missing from the result.

from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        adj = [[] for i in range(numCourses)]
        indegree = [0] * numCourses
        for nxt, pre in prerequisites:
            indegree[nxt] += 1
            adj[pre].append(nxt)

        output = []

        def dfs(node):
            output.append(node)
            indegree[node] -= 1
            for nei in adj[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    dfs(nei)

        for i in range(numCourses):
            if indegree[i] == 0:
                dfs(i)

        return output if len(output) == numCourses else []

class Solution {
    vector<int> output;
    vector<int> indegree;
    vector<vector<int>> adj;

    void dfs(int node) {
        output.push_back(node);
        indegree[node]--;
        for (int nei : adj[node]) {
            indegree[nei]--;
            if (indegree[nei] == 0) {
                dfs(nei);
            }
        }
    }

public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        adj = vector<vector<int>>(numCourses);
        indegree = vector<int>(numCourses, 0);
        for (auto& pre : prerequisites) {
            indegree[pre[0]]++;
            adj[pre[1]].push_back(pre[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                dfs(i);
            }
        }

        if (output.size() != numCourses) return {};
        return output;
    }
};