Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

151. Redundant Connection

MediumDay 44 of 60Graphs

A tree with n nodes labelled 1 to n had exactly one extra edge added, so the graph now contains one cycle. You are given the edges in edges as pairs [a, b]. Return an edge whose removal turns the graph back into a tree. If several edges qualify, return the one that appears last in the input.

Example 1
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Nodes 1, 2 and 3 form a triangle. Removing [2,3], the last edge of the cycle, leaves a tree.
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 <= a < b <= n (or any order)
  • No repeated edges, the graph is connected
Hints
Frequently asked at: Amazon, Google, Uber
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for ₹200/ 30 min