← Visualizers
Graphs · 1.F / 2.E · the union-find atom LeetCode 684

Redundant Connection / visualized

n nodes, n edges — a tree plus exactly one extra. Walk the edges in order and ask one question of each: are these two ends already in the same component? The first edge for which the answer is yes is the redundant one. The structure that answers it is a forest of parent pointers, drawn here beside the graph, so that find climbing to a root and union re-rooting are things you watch rather than infer.

Execution

idle
the graph · edges as given
the DSU forest · parent pointers
Press Run to begin.
0 / 0
Speed

Java · running line

endpoint u endpoint v where find is standing set root / united edge edge not yet considered
O(n·α(n)) time, O(n) space — effectively linear  ·  union by size and path compression are not tuning. Drop them and find walks a chain instead of a stub: the same answer, arrived at in O(n²). Flip the toggle and read the two numbers in the second card.