PreviousNext
Coding/Graphs and trees

Redundant edge in tree

Write codeMedium25 min

Your task

A connected undirected graph that started as a tree on n nodes (labeled 1..n) had exactly one extra edge added, creating exactly one cycle. You are given the n edges as [u, v] in the order they were added. Return the one edge that can be removed so the result is a tree; if multiple answers, return the edge that appears last in the input. Nodes are 1-indexed.

Examples

redundant_edge(edges: list[list[int]]) -> list[int]
Example 1
Inputredundant_edge([[1, 2], [1, 3], [2, 3]])
Output[2, 3]