The Runtime Theory
mediumLeetCode#union-find#cycle-detection

Redundant Connection

Find the edge that first closes a cycle as edges are added to an undirected graph.

The Runtime Theory Team25 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

inedges=[[1,2],[1,3],[2,3]]

out[2,3]

inedges=[[1,2],[2,3],[3,4],[1,4],[1,5]]

out[1,4]

inedges=[[1,2],[2,3],[3,1]]

out[3,1]

Find the edge that first closes a cycle as edges are added to an undirected graph.

A good solution should

  • State the invariant or decision rule that makes the approach correct.
  • Explain time and space costs in terms of input size and required output.
  • Handle empty, minimal, duplicate, and boundary-shaped inputs.

Reasoning prompt

Use disjoint-set union; an edge is redundant when its endpoints already have the same representative.

Use the linked judge for the canonical challenge. The examples above are compact TRT checks; create additional tests around the boundary most likely to break your invariant.

More practice in this topic

hard · graphsAlien Dictionarymedium · graphsCheapest Flights Within K Stopsmedium · graphsClone Graph

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save