Coding questions · Apple

Find the Extra Edge

This question evaluates understanding of graph theory concepts—cycle formation and edge connectivity—and the competency in applying graph algorithm techniques to identify and remove a redundant edge in an undirected graph.

You are given an undirected graph that started as a tree with n nodes labeled from 1 to n. One additional edge was then added between two different existing nodes, creating exactly one cycle.

You are given an array edges, where edges[i] = [u, v] represents an undirected edge between nodes u and v. Return the edge that can be removed so that the remaining graph is a tree again.

If multiple edges could be removed, return the one that appears last in the input order.

Example

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

Constraints

n == edges.length
3 <= n <= 1000
1 <= u, v <= n
u != v
The input graph is connected and contains exactly one cycle.

Find the Extra Edge

Hints

A tree has no cycles. As you process edges one by one, what does it mean if the two endpoints are already connected?
Use a Disjoint Set Union (Union-Find) structure to track connected components efficiently while scanning the edges in input order.