210. Course Schedule II

Depth-First Search Breadth-First Search Graph Topological Sort

Intuition

Finding a valid course order is exactly topological sorting of a directed graph. Kahn's algorithm (BFS-based) is the cleaner approach: start with all courses that have no prerequisites (in-degree 0), process them one by one, and "unlock" courses whose last prerequisite has just been completed. If a cycle exists, some courses will never reach in-degree 0.

Algorithm

1Build adjacency list and in-degree array from prerequisites.
2Enqueue all nodes with in-degree 0.
3Dequeue a course: add it to the result order. For each neighbour, decrement its in-degree.
4If a neighbour's in-degree reaches 0, enqueue it.
5If result.Count == numCourses, return result. Otherwise a cycle exists - return [].

Example Walkthrough

Input: numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]

1.In-degrees: 0->0, 1->1, 2->1, 3->2. Queue: [0].
2.Dequeue 0: result=[0]. Decrement 1 (->0), 2 (->0). Queue: [1,2].
3.Dequeue 1: result=[0,1]. Decrement 3 (->1). Queue: [2].
4.Dequeue 2: result=[0,1,2]. Decrement 3 (->0). Queue: [3].
5.Dequeue 3: result=[0,1,2,3]. Count=4=numCourses -> valid.

Output: [0,1,2,3]

Common Pitfalls

•A cycle is detected by checking result.Count < numCourses at the end, not during BFS.
•The order returned is one valid topological order - many valid orderings may exist.
•Build the graph so edges point FROM prerequisite TO the course that requires it (forward direction).

210.cs

// Approach: Kahn's BFS-based topological sort to find a valid course ordering.
// Build an adjacency list and compute the in-degree (number of prerequisites) for each course.
// Enqueue all courses with in-degree 0 — these have no prerequisites and can be taken immediately.
// Dequeue a course, add it to the result, and reduce the in-degree of all its dependent courses.
// Any dependent that reaches in-degree 0 is enqueued as it is now unblocked.
// If the result contains all numCourses nodes, return it; otherwise a cycle exists — return empty.
// Time: O(V + E) where V = numCourses and E = prerequisites count. Space: O(V + E).

public class Solution
{
    public int[] FindOrder(int numCourses, int[][] prerequisites)
    {
        List<List<int>> adj = new List<List<int>>();

        for (int i = 0; i < numCourses; i++)
            adj.Add(new List<int>());

        for (int i = 0; i < prerequisites.Length; i++)
        {
            int node1 = prerequisites[i][0];
            int node2 = prerequisites[i][1];
            adj[node2].Add(node1);
        }

        return BFSFindOrder(adj, numCourses);
    }

    private int[] BFSFindOrder(List<List<int>> adj, int v)
    {
        int[] inDegree = new int[v];

        for (int i = 0; i < v; i++)
        {
            foreach (int adjNode in adj[i])
                inDegree[adjNode]++;
        }

        Queue<int> q = new Queue<int>();
        for (int i = 0; i < v; i++)
        {
            if (inDegree[i] == 0)
                q.Enqueue(i);
        }

        List<int> ans = new List<int>();
        while (q.Count > 0)
        {
            int node = q.Dequeue();
            ans.Add(node);

            foreach (int adjNode in adj[node])
            {
                inDegree[adjNode]--;
                if (inDegree[adjNode] == 0)
                    q.Enqueue(adjNode);
            }
        }

        if (ans.Count == v)
            return ans.ToArray();
        return new int[] { };
    }
}

Was this solution helpful?