Redundant Connection Medium 0 attempts
LeetCode ↗

Redundant Connection

Medium TreeBinary TreeDFS LeetCode

You're given an undirected graph that was originally a tree but gained one extra edge, which introduced a cycle. Return an edge whose removal restores a tree. If multiple edges qualify, return the one occurring last in the input edge list.

Input Format
Implement findRedundantConnection(edges). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
edges = [[1,2],[1,3],[2,3]]
Output
[2,3]

Example 2

Input
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output
[1,4]
Constraints
  • n == edges.length
  • 3 <= n <= 1000
  • 1 <= edges[i][0] < edges[i][1] <= n
Test Cases (2)
Case 1
Args: [[[1,2],[1,3],[2,3]]] Expected: [2,3]
Case 2
Args: [[[1,2],[2,3],[3,4],[1,4],[1,5]]] Expected: [1,4]
Topics
TreeBinary TreeDFS

Union-Find

javascript
function findRedundantConnection(edges) {
  const parent = Array.from({length: edges.length+1}, (_,i) => i);
  const size = Array(parent.length).fill(1);
  function find(x) { while(parent[x]!==x){parent[x]=parent[parent[x]];x=parent[x];}return x; }
  function union(a,b) { a=find(a);b=find(b);if(a===b)return;if(size[a]<size[b])[a,b]=[b,a];parent[b]=a;size[a]+=size[b]; }
  for (const [u, v] of edges) {
    if (find(u) === find(v)) return [u, v];
    union(u,v);
  }
}

Time: O(n α(n)) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript