THE CONNECTED COMPONENTS — a dart

CONNECTED COMPONENTS how many islands? — count the separate pieces of a graph

The connected components of a graph are its separate islands — maximal groups of nodes reachable from each other. Counting them answers “how many separate networks are here?”: distinct social circles, disconnected clusters, isolated regions of a map. Union-find makes it a one-liner: merge every edge, then count the distinct roots — each root is one island. (DFS/BFS do it too, starting a new search from each unvisited node.) A graph with edges 0-1, 1-2, and 3-4 has two components: {0, 1, 2} and {3, 4}.

THE TECHNIQUE union every edge, count the roots — each root is one component

The demo unions the edges 0-1, 1-2, 3-4 and counts the components — 2 islands: live demo

HISTORY & CREDIT connected components · union-find / BFS

“A graph is one connected thing.” — often it is several islands; counting the union-find roots tells you how many. cited

the merge · union every edge’s endpoints — reachable nodes collapse into one set.
the count · the number of distinct roots = the number of islands.
the alternative · a fresh DFS/BFS from each unvisited node counts the same components.

A graph’s separate islands counted by the roots that remain — how many networks in one picture. resource

RECOMMEND FOR I-13 the island count, on the compiler

On the canonical compiler, edges 0-1, 1-2, 3-4 give 2 components ({0,1,2} and {3,4}):

$ i13 run nw_connectedcomponents.i13 # union edges, count roots RUN OK · 462 step(s) · peak stack 8 · call depth 6 components = 2 -- {0,1,2} and {3,4}

Recommend as a NULL — a computed count. The number of connected components is a computed property of the graph (forall-pinned, B39), found by union-find or traversal (B40). No new invariant. NULL — the islands, counted by the roots that survive.