Topological Sort

In-degree = how many arrows point into a vertex = how many things it is still waiting for. For prerequisites [[1,0],[2,0],[2,1]] (arrows 0→1, 0→2, 1→2): course 0 has in-degree 0, course 1 has 1, course 2 has 2. In-degree 0 means nothing is pending, so it can go next. Each time a vertex is output, its neighbours lose one pending prerequisite: indegree[v]--.

No — plain BFS orders vertices by distance from the start, not by dependencies. Edges 0→1, 0→2, 2→1: if 0's list is [1, 2], BFS from 0 visits 1 before 2 (both are one hop away), but 2 → 1 says 2 must come first. Kahn looks like BFS, but a vertex joins the queue only when its in-degree hits 0 — when all its prerequisites are done, not when it is first seen.

Take a cycle a → b → c → a. In any list, one of these three appears first, say a. But c → a says c must come before a. Contradiction — so no order can satisfy all edges.

When u finishes, every vertex u points to has already finished — it was either black before we got there or we finished it during u's own DFS (it can't be gray, or that would be a cycle). So for every edge u → v, v is pushed before u. Reversing puts u before v — exactly what we need.

Kahn by default: it's iterative (no stack overflow), the cycle check is a counter, and it upgrades easily to PriorityQueue (smallest order) and DP (longest path). Use DFS when you already have a DFS skeleton or need per-vertex results like "safe" states.

In a directed graph, reaching a vertex you finished earlier is fine (e.g. two courses share a prerequisite). Only reaching a vertex that is still on the current path (gray) means you went in a circle. Two states can't tell those apart.

Still fine — the order just mixes the pieces in some way. Kahn: seed the queue with every in-degree-0 vertex, not only vertex 0; a lonely vertex has in-degree 0 and comes out right away. DFS: start a new DFS from every vertex that is still white. Miss this and your output is shorter than V, which looks like a fake cycle.

Yes, with DFS and a parent[] array. When an edge u → v hits a gray v, the cycle is v → … → u → v: walk parent back from u until you reach v. Kahn can't do this cleanly — its leftover vertices are the ones on a cycle plus everything that depends on one (can be reached from it).

Possibly a huge number — a graph with no edges has V! orders. Counting them exactly is a known hard problem in general (#P-complete, proved by Brightwell and Winkler in 1991). The order is unique exactly when Kahn's queue never holds more than one vertex at a time.

No — problems like Course Schedule II accept any valid order. The judge checks that every prerequisite comes first. Only problems that ask for a specific order (e.g. smallest) need a PriorityQueue.

Think of a normal dictionary: "cat" comes before "dog" only because c < d. The letters after that (a vs o) were never compared, so they prove nothing. Neighbours are enough because sorted order chains: if w1 ≤ w2 and w2 ≤ w3, then w1 ≤ w3. So any letter order that keeps every neighbouring pair in order keeps the whole list sorted. Comparing far-apart pairs only repeats what the neighbour rules already imply.

Safety depends on where you can go: a node is safe when every outgoing edge leads to a safe node. Kahn frees a vertex when its incoming count hits 0. Flip every edge and "all my exits are safe" becomes "all my incoming edges are done" — terminal nodes become the starting sources. The counter is simply outdegree[u] from the original graph.

Not as such — an undirected edge has no "before". But the same peeling idea works on trees: Minimum Height Trees removes degree-1 leaves layer by layer, exactly like Kahn removes in-degree-0 vertices.

Both ends of the longest path must shrink at the same speed. Path 0-1-2-3-4, one leaf at a time: remove 0, then 4, then 1 — now only 2 and 3 remain, so you stop and return [2, 3]. The right answer is [2]. Layer by layer: remove {0, 4}, then {1, 3}, and only 2 is left. Dhyan do: count the current layer's size before you start removing it.