Basic Questions — Union Find

Question 1 — Trace naive union

Start with parent = [0, 1, 2, 3, 4] (5 singletons). Apply these unions in order using the naive template (no rank, no path compression, always parent[rx] = ry):

union(0, 1), union(2, 3), union(0, 2), union(0, 4).

What is the final parent array? What is find(0)?

Question 2 — Same trace, with path compression

Same start and same sequence, but use path compression in find. What’s the final parent array, and what’s find(0) after the last union?

Question 3 — Trace union by rank

5 singletons. Apply union by rank (without path compression):

union(0, 1), union(2, 3), union(0, 2).

Show the parent and rank arrays after each step.

Question 4 — Cycle detection

Given vertices {0, 1, 2, 3} and edges arriving in this order: (0, 1), (1, 2), (2, 3), (3, 0). Use DSU to detect when a cycle is formed.

Question 5 — Counting components

A graph has 6 vertices {0, 1, 2, 3, 4, 5} and edges (0, 1), (2, 3), (4, 5), (0, 2). How many connected components are there?

Question 6 — When NOT to use DSU

You’re asked: “given a directed graph, return all vertices reachable from vertex s.” Can DSU solve this?