noodleProblems/
Redundant Connection
#170

Redundant Connection

AlgorithmmediumUnion FindGraph

A tree is an undirected, connected graph with n nodes and exactly n - 1 edges and no cycles. You are given a graph on n nodes, labelled 1 to n, that started as a tree and had **one extra edge added**, given as edges, a list of n [u, v] pairs (so the graph has n edges and exactly one cycle).

Return the edge that can be removed so that the remaining n - 1 edges form a tree again. If more than one edge could be removed, return the one that occurs **last** in edges.

Example cases

  • triangle
    in edges =
    12
    13
    23
    out [2,3]
    1-2 and 1-3 form a tree; 2-3 closes the cycle and is the last edge that does so.
  • cycle plus a branch
    in edges =
    12
    23
    34
    14
    15
    out [1,4]
    1-2-3-4 plus 1-4 closes a cycle; 1-5 is a harmless branch off the tree.
  • cycle formed early
    in edges =
    12
    23
    13
    34
    45
    out [1,3]
    1-2 and 2-3 form a tree; 1-3 closes the cycle. The remaining edges just extend the branch.

Constraints

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= u, v <= n
  • u != v
  • There are no repeated edges.
  • The given graph is connected and contains exactly one cycle.
Saved
edges =
[[1,2],[1,3],[2,3]]