MediumGraphs · Union-find

Graph Valid Tree

Given n nodes labelled 0 to n − 1 and a list of undirected edges, return whether they form a valid tree: every node connected, and no cycle. There are no self-loops or repeated edges.

5, [[0,1],[0,2],[0,3],[1,4]] → true5, [[0,1],[1,2],[2,3],[1,3],[1,4]] → false

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; nodes laid out by distance from 0

current nodetree edgeedge being checkedcloses a cycle

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]]. Separate pieces of a disconnected graph are drawn side by side.