Redundant Connection

Union find · Merge groups and detect an existing connection · Stretch · about 27 min

Why it matters

This is the clean tool for dynamic connectivity and cycle checks in undirected graphs.

How it connects

DFS can discover components by walking them. Union find maintains components as edges arrive.

Try first

When does adding an edge create a cycle in terms of its two endpoints’ groups?

Interview cue

Union find detects whether an edge joins two different components without traversing the graph again.