MediumGraphs · Union-find

Number of Connected Components in an Undirected Graph

An undirected graph has n nodes labelled 0 to n − 1, and edges[i] = [a, b] connects a and b. Return the number of connected components: groups of nodes that can reach each other.

5, [[0,1],[1,2],[3,4]] → 25, [[0,1],[1,2],[2,3],[3,4]] → 1

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

Graph

Undirected edges; each component drawn in its own block

current nodeedge that reached a new node / joined two setsedge being checked

Time and space complexity

V = n, E = number of edges. The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. Up to 9 nodes and 14 edges, written like [[0,1],[1,2]]. Each component is drawn in its own block, left to right.