Can node A reach node B? In a static graph, run DFS once: . Simple.
But what if edges arrive over time and you need to answer connectivity queries after each one? DFS from scratch each time is too slow.
Union-Find answers "are these connected?" in nearly time. It handles dynamic edge additions efficiently. I'll show you when DFS suffices, when you need Union-Find, and how to apply path compression and union by rank. These two tools cover most connectivity problems you'll encounter.
