Micro-questions over the connected components module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The vocabulary
1. What is a connected component?
Answer
A maximal set of vertices that can all reach one another — maximal meaning you cannot add another vertex without breaking the property.
2. What guarantee do components give about coverage?
Answer
Every vertex is in exactly one component, so the components partition the graph — nothing left over, nothing counted twice.
3. What is an isolated vertex?
Answer
A vertex with no edges. It forms a component by itself.
4. What is flood fill?
Answer
Starting at one vertex and traversing everything reachable, marking as you go. One flood fill discovers exactly one component, so the number of times you must start a fresh one is the component count.
5. What is union-find?
Answer
Also disjoint-set union (DSU) — a structure maintaining a partition under find (which group is this in?) and union (merge these two groups). See union-find.
6. What is a redundant edge, and what does it mean?
Answer
An edge whose endpoints are already in the same component. It merges nothing. In a graph built only from merging edges, a redundant edge is exactly a cycle.
7. What is incremental / dynamic connectivity?
Answer
The setting where edges arrive over time and you must answer after each one. It is the case that decides between traversal and union-find.
B. Flood fill
8. How do you count components with DFS or BFS?
Answer
Loop over all vertices. For each one not yet visited, increment a counter and flood-fill from it.
9. What is the cost?
Answer
in total, regardless of how many components there are.
10. Why must the outer loop run over vertices and not edges?
Answer
Isolated vertices have no edges, so iterating over edges never sees them and you undercount.
11. Does DFS or BFS give a different answer?
Answer
No — same components, same count. BFS additionally gives you the fewest-edges path between vertices for free, which is the only reason to prefer it here.
C. Union-find and the counting identity
12. What does union-find assume at the start?
Answer
That nothing is connected: components, everyone alone.
13. What happens per edge?
Answer
Either it joins two different groups — the count drops by one — or it joins two vertices already together and changes nothing.
14. State the counting identity.
Answer
15. Seven teams, three merging meetings — how many clusters?
Answer
.
16. What is the first thing that falls out of the same counter for free?
Answer
Cycle detection. union returning False is “this edge creates a cycle” — which is exactly how Kruskal’s algorithm avoids them.
17. What is the second?
Answer
“Is this a tree?” — a graph is a tree iff the count reaches 1 and every edge merged (i.e. connected with edges).
18. What is the cost per union-find operation?
Answer
With path compression and union by rank, effectively — an amortised result needing a potential argument to prove, and below 5 for any that will ever exist.
D. Choosing a method
19. 2,000 teams, meetings arriving one at a time, report clusters after each — is re-running DFS acceptable?
Answer
No. The lab measures union-find at 0.0026s against DFS re-runs at 1.2407s over 600 edges — about 500× slower, and the gap grows with both and .
20. Why is the gap structural rather than a constant factor?
Answer
Re-running DFS is per edge, so overall. Union-find pays per edge and never recomputes anything.
21. Give the full decision table.
Answer
| Situation | Use |
|---|---|
| All edges known, one answer needed | DFS or BFS |
| Edges arrive over time | union-find |
| Need the path between two vertices | BFS |
| On a grid | DFS/BFS flood fill |
| Edges are also removed | neither |
22. Why is “edges removed” the real limitation?
Answer
Union-find cannot un-merge. There is no split, because path compression has destroyed the information about which edge joined what.
23. What do you need instead if edges can disappear?
Answer
Dynamic connectivity — considerably heavier machinery (link-cut trees, Euler tour trees) or a rebuild from scratch.
24. Why prefer a traversal when you need the actual members?
Answer
Union-find works but you must group by root afterwards; a single DFS hands you the groups directly and is simpler.
E. Directed graphs
25. What two questions does “connected” split into once edges have direction?
Answer
Weakly connected — components computed by ignoring direction. Strongly connected — sets that can all reach each other respecting direction.
26. On a→b, b→c, c→a, c→d, d→e, e→d, give both answers.
Answer
Weak: 1 component, [a, b, c, d, e]. Strong: 2 — [a, b, c] and [d, e], because d and e are reachable from the others but cannot get back.
27. Is choosing between them an algorithmic or a modelling question?
Answer
A modelling question. “Which teams share information at all?” is weak; “which teams can all reach each other?” is strong. Asking for “the connected components” of a directed graph without saying which is ambiguous — and a reasonable thing to ask an interviewer to clarify.
28. How do you compute weak components?
Answer
Just run the undirected algorithm on the underlying undirected graph.
29. Describe Kosaraju’s algorithm.
Answer
One DFS to order vertices by decreasing finish time, then a second DFS on the reversed graph. Each tree of that second forest is one SCC. .
F. Traps
30. Seven teams, three meetings — why is “two clusters” wrong?
Answer
Because lone vertices are components too. The answer is four.
31. What breaks on a 5,000-vertex chain?
Answer
Recursive DFS — about 1,000 frames in CPython, so one component and one RecursionError. Use the explicit stack.
32. What must union report, and what breaks if it does not?
Answer
Whether it actually merged. Incrementing blindly breaks both the component count and the cycle detection built on it.
33. Summarise the lesson in one sentence.
Answer
Count components by flood fill when the graph is fixed and by union-find when edges arrive — and the moment edges can also be removed, neither works.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Connected Components — the module
- Union-Find — the incremental structure
- Minimum Spanning Tree — where
unionreturning False becomes cycle avoidance
Software engineering
Infrastructure & security
Computer science
Hardware & engineering