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
SituationUse
All edges known, one answer neededDFS or BFS
Edges arrive over timeunion-find
Need the path between two verticesBFS
On a gridDFS/BFS flood fill
Edges are also removedneither

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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Graph Algorithms