Redundant Connection
Medium · Graphs · about 20 minutes
Asked at Google, Amazon, Uber.
A tree with n nodes labeled 1..n had one extra edge added, creating exactly one cycle. Given the edges list (in the order given), return the edge that can be removed so the graph becomes a tree again. If several edges qualify, return the one that appears last in the input.