We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Union-find keeps a forest of disjoint sets with near-constant find and union once you add path compression and union by rank. It beats DFS whenever connectivity queries are interleaved with edge additions, and it detects cycles in an undirected graph almost incidentally. Short to implement, and instantly recognisable to an interviewer as the right tool.
"Are these two connected?", counting components, or detecting a cycle in an undirected graph.
5 problems. Each one runs in an in-browser editor against real test cases, with hints and a worked solution.
The patterns cheat sheet covers all of these in one page - what each one looks like in a problem statement, and the template that follows.