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
| Feature | Union-Find | DFS / BFS |
|---|---|---|
| Incremental edges | per edge | per query |
| Check membership | ||
| Retrieve the path | cannot | returns the exact path |
| Edge deletion | cannot | must 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
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Union-Find — the module
- Connected Components — Question Bank
- MST — Question Bank — Kruskal’s use of it
Software engineering
Infrastructure & security
Computer science
Hardware & engineering