Union-find and topological sort

Topological sort handles "this must come before that". A node is ready once everything it depends on is done. Start a queue with the nodes that depend on nothing. Take one, and lower the count for each node that depends on it. Every node you take has nothing left blocking it.

If you take fewer than V nodes, the rest contain a cycle. There can be several valid orders. If the problem asks for the alphabetically smallest order, use a min-heap instead of a queue; otherwise, a plain queue gives a valid order.

The same order supports DP. For the longest path in a graph with no cycles, push each node's best answer along its outgoing edges once everything before it is settled. The graph doesn't have to look like a network: in a grid, "move to a bigger neighbor" makes a graph with no cycles.

Union-find answers a different question: as edges are added, which elements are in the same connected group? Each group has a root. find follows parent links up to the root, and union links two roots. With path compression and union by size, each operation takes nearly O(1) time on average. The exact bound is O(α(n)), where α grows so slowly it's below 5 for any real input S12.

What stays true: two elements have the same root exactly when the edges added so far connect them. The parent links inside a group are bookkeeping, not the graph's real edges. The root has no special meaning unless you choose to store something there.

Plain union-find only handles groups that grow. It can't undo a merge. If you know every operation in advance, you can sometimes run time backward so deletions become additions. Otherwise you need extra machinery to roll back. And union-find doesn't capture one-way reachability in a directed graph.

Practice: LC 207 Course Schedule, LC 210 Course Schedule II, LC 329 Longest Increasing Path in a Matrix, LC 684 Redundant Connection, LC 721 Accounts Merge, LC 547 Number of Provinces.

Check your understanding: Is the relation one-way ("before") or two-way ("connected")? Can groups split later? What extra data, like a group's size, must you combine when groups merge?