Connected Components

What is this?

A component is a set of things that can all reach each other and nothing outside. Finding them is the easy part — a flood fill from every unvisited node. What makes these problems interesting is what you do with the components once you have them: count the pairs they cannot form, decide which are safe, merge them with a budget, or ask what a single change would create.

That last one is the key skill. Rather than re-flooding after every hypothetical change, label each component once and answer every hypothetical with arithmetic.

💡 Fun fact: Making A Large Island is the clearest example of "precompute, then answer instantly". Flipping each 0 and re-flooding is O(n⁴) on an n × n grid. Instead, label every island with a unique id and record its size in one pass; then for each 0, sum the sizes of the distinct ids around it and add one. That is O(n²) — and the word "distinct" is load-bearing, because two neighbouring cells frequently belong to the same island and would otherwise be counted twice.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: find the components once, record what you will need about them — size, id, whether they touch a boundary — and then answer the actual question with arithmetic instead of more traversals.

1. Counting what is not connected

Count Unreachable Pairs asks for the number of node pairs that cannot reach each other. Enumerating them is O(n²). Counting them is subtraction:

total pairs        = n(n-1)/2
pairs within a component of size s = s(s-1)/2
unreachable        = total - sum over components of s(s-1)/2

Or, walking the components once and accumulating already_seen × current_size as each is discovered — same result, one pass, no overflow risk from the big subtraction.

2. Sealing regions that touch the edge

Number of Enclaves wants land cells that cannot walk off the grid. Rather than testing each region for an escape route, flood inward from the border first and mark everything reachable, then count what remains. The inversion — starting from the outside rather than the inside — is the same trick that makes Pacific Atlantic Water Flow tractable: flood from each ocean's edge, and the answer is the cells reached by both floods.

3. Spending a budget of edges

Number of Operations to Make Network Connected is a counting argument dressed as a graph problem. With n computers and k components, joining them all requires exactly k − 1 cables — and a cable is spare whenever an edge connects two already-connected machines. So: if edges < n − 1 it is impossible; otherwise the answer is components − 1. You never need to decide which cable to move.

4. A 30-second worked example (Making A Large Island)

grid          labels + sizes
1 0           island A = {(0,0)}        size 1
0 1           island B = {(1,1)}        size 1

for each 0:
  (0,1): neighbours are A (left) and B (below) → 1 + 1 + 1 = 3
  (1,0): neighbours are A (above) and B (right) → 1 + 1 + 1 = 3
                                          answer = 3

And the reason "distinct" matters — a different grid:

1 1 0        island A = {(0,0),(0,1),(1,0)}   size 3
1 0 0
0 0 0

cell (1,1): neighbours above (A) and left (A) — the SAME island
            counting both gives 3 + 3 + 1 = 7  ✗
            counting distinct ids gives 3 + 1 = 4  ✓

5. Where you'll actually meet this

• Network topology. Counting isolated segments and the minimum links needed to unify them is the cable problem exactly.
• Image processing. Connected-component labelling is a standard operation — the same "label once, query many times" structure.
• Geospatial analysis. Watershed and drainage modelling is Pacific Atlantic Water Flow at real scale, and it is solved the same way, from the boundary inward.
• Social graphs. Counting cross-community pairs, or the reach of a merge between two communities.
• Game maps. Determining enclosed territory — the Go rules for captured stones are the enclaves problem.

6. Problems in this chapter

▶ Count Unreachable Pairs of Nodes in an Undirected Graph

Count node pairs with no path between them. Find component sizes, then subtract within-component pairs from the total.
Pattern: component sizes + counting arithmetic. Target: O(V + E) time, O(V) space.

▶ Number Of Enclaves

Count land cells that cannot reach the border. Flood inward from every border land cell, then count what was never reached.
Pattern: flood from the boundary, invert. Target: O(mn) time, O(mn) space.

▶ Number of Operations to Make Network Connected

Minimum cable moves to connect every computer. Impossible if edges < n − 1; otherwise components − 1.
Pattern: component count + a feasibility check. Target: O(V + E) time.

▶ Making A Large Island

Flip one 0 to 1 to make the largest island. Label and size every island in one pass, then evaluate each 0 by summing its distinct neighbouring islands.
Pattern: label once, answer by arithmetic. Target: O(mn) time, O(mn) space.

▶ Pacific Atlantic Water Flow

Cells draining to both oceans. Flood from each ocean's border inward against the gradient, then intersect the two reachable sets.
Pattern: reverse flood from two sources. Target: O(mn) time, O(mn) space.

7. Common pitfalls 🚫

• Re-flooding for every hypothetical. Label once; the whole point of Making A Large Island is avoiding the extra passes.
• Forgetting "distinct". Two neighbouring cells often belong to the same island, and double-counting is the classic wrong answer.
• Missing the all-ones grid. If there are no zeros to flip, the answer is the whole grid — a case that crashes solutions assuming at least one flip.
• Flooding forward instead of from the boundary. Both the enclaves and water-flow problems become far harder if you start inside.
• Getting the water-flow direction backwards. Flooding from the ocean means moving to cells of equal or greater height, since you are going against the flow.
• Integer overflow on pair counts. n(n−1)/2 for n = 10⁵ exceeds 32 bits.
• Marking visited on dequeue rather than enqueue. The same cell then enters the queue several times and the counts drift.

8. Key takeaways

1. Find components once, then reason about them — sizes, ids and boundary flags answer most follow-up questions without another traversal.
2. Count the complement. Unreachable pairs are total pairs minus within-component pairs.
3. Flood from the boundary when the question is about what cannot escape.
4. components − 1 edges join everything, provided you have the spares.
5. Distinct neighbours, always, when summing adjacent regions.
6. Reverse the flow in water-flow style problems — start at the destination and go against the gradient.
7. Why interviewers like it: the flood fill is assumed. What they are watching is whether you precompute the right facts and turn the actual question into arithmetic.

Order: Count Unreachable Pairs → Number Of Enclaves → Number of Operations to Make Network Connected → Making A Large Island → Pacific Atlantic Water Flow.