Topological Sort

Opening scenario

Problem references use LC for LeetCode.

Course Schedule II (LC 210): numCourses courses labeled 0..n-1 and a list of prerequisite pairs [a, b] meaning b must be taken before a. Return an ordering of all courses you can take to finish them all, or [] if impossible. Follow-up you should expect: Alien Dictionary (LC 269) — given words sorted in an unknown alphabet's lexicographic order, return a possible ordering of the letters.

Here n = numCourses; return any valid ordering when several exist. For Alien Dictionary, include every distinct letter appearing in the input, and return an empty string if the ordering constraints conflict. Begin with one prerequisite pair and decide which direction its edge must point.

Question progression

Q1 — What does "b before a" actually constrain, and what structure encodes it?

Question: You're handed pairs like [a, b] = "b before a". What graph does this describe, and what does a valid course order correspond to in that graph?