Micro-questions over the union-find module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The object

1. What is union-find?

Answer

A structure for tracking which things are grouped together, when groups can only ever merge and never split. Also called disjoint set union (DSU).

2. What are disjoint sets?

Answer

A collection of groups where nothing belongs to more than one. Every element is in exactly one group at any moment.

3. What is a representative, and what is the entire trick?

Answer

One chosen member standing for the whole group — also called the root or leader. Two elements are in the same group exactly when they have the same representative, so membership is one comparison rather than a search.

4. What is a parent pointer?

Answer

A reference from each element to another in its group. Following parents repeatedly reaches the representative, which is its own parent.

5. What is find?

Answer

The operation returning an element’s representative, by following parent pointers to the top.

6. What is union?

Answer

The operation merging two groups, by making one group’s representative point at the other’s.


B. The two optimisations

7. What is path compression?

Answer

Applied during find: once you have walked up to the representative, go back and point every element you passed directly at it. It makes the structure flatter every time you use it.

8. What is union by rank?

Answer

When merging, always attach the shorter tree underneath the taller one, so the result never gets deeper than it needs to be.

9. What is union by size, and how does it compare?

Answer

Attach the smaller group under the larger. A close relative that works just as well.

10. What happens without either optimisation?

Answer

The trees degenerate into linear chains — effectively linked lists — and find becomes .

11. What does union by rank alone bound the height to?

Answer

.

12. What does path compression alone achieve?

Answer

It flattens the tree toward near-constant depth on repeated access — but without rank you can still build a tall tree before compressing it.


C. The complexity

13. What is the inverse Ackermann function?

Answer

Written — the per-operation cost once both optimisations are used. It grows so extraordinarily slowly that it is less than 5 for any you could ever store.

14. Is union-find genuinely ?

Answer

No — strictly it is not. It is treated as constant in practice, but the honest statement is amortised, which requires a potential argument to prove.


D. The ADT

15. List the union-find ADT.

Answer

make_set(x) ; find(x) ; union(x, y) ; connected(x, y) — just find(x) == find(y); count() — separate groups remaining.

16. How is count() maintained?

Answer

Start it at the number of elements and decrement on every successful union.

17. What should union return, and why does it matter?

Answer

Whether a merge actually happened. If x and y were already together, that is a useful signal — and it is exactly how Kruskal’s algorithm detects an edge that would create a cycle.

18. Do you usually care about the representative’s identity?

Answer

No — only that two elements sharing one are in the same group. Which element is chosen is an implementation detail.


E. The restriction

19. Why is there no split operation, and why can there not be one?

Answer

Path compression works by discarding the history of how groups were built — it rewires pointers straight to the representative — so the information needed to undo a merge is deliberately thrown away. That is precisely what makes it so fast.

20. Name four problems where union-find is the right structure.

Answer

Building a minimum spanning tree; detecting a cycle as edges arrive; counting connected components in a growing graph; grouping accounts as duplicates are discovered.

21. What do those four have in common?

Answer

Connections are only ever added.

22. What do you do if connections can be removed?

Answer

Recompute components with DFS or BFS, or reach for a considerably more complex dynamic-connectivity structure.


F. Cycle detection

23. State the cycle-detection insight.

Answer

If union(u, v) returns False, u and v were already connected through another path — so adding edge (u, v) creates a cycle.

24. What two things does that single property power?

Answer

Kruskal’s MST (add cheapest edges, skip any where union returns False) and redundant-edge detection (find the single edge creating an unwanted cycle).

25. Does this work for directed graphs?

Answer

No. Union-find has no notion of direction — it only knows “connected”. Directed cycle detection needs DFS back edges.


G. Union-find vs traversal

26. Compare the two across four rows.

Answer
FeatureUnion-FindDFS / BFS
Incremental edges per edge per query
Check membership
Retrieve the pathcannotreturns the exact path
Edge deletioncannotmust re-traverse

27. What is the one thing union-find fundamentally cannot give you?

Answer

The route. It knows two things are connected; it has no idea how.

28. Summarise union-find in one sentence.

Answer

Track group membership by pointing everything at a representative and flattening as you go — effectively constant per operation, and permanently unable to un-merge or tell you the path.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Data Structures — University-Style Teaching Notes