Medium
Kahn's algorithm on a graph containing a cycle
Kahn's algorithm repeatedly removes a vertex with in-degree 0, appends it to the output, and decrements the in-degree of its neighbors, enqueuing any neighbor whose in-degree drops to 0. Run on a graph containing the cycle A→B→C→A (plus possibly other acyclic vertices), what does the algorithm observe, and how does that reveal the cycle?
20 of 46 in Data Structures & Algorithms