MediumGraphs · Union-find

Redundant Connection

A tree on nodes 1 to n had one extra edge added, so edges has length n and contains exactly one cycle. Return an edge you can remove to get a tree again; if several work, return the one that appears last in edges.

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

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; laid out by distance from node 1

current nodeon the cyclenot added yetedge being checkedanswer

Time and space complexity

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

Keyboard: ← → step, Space play or pause. Enter 3 to 9 edges like [[1,2],[2,3],[1,3]]; with n edges the nodes are 1 to n, and the graph must be a connected tree plus one extra edge.