Find the Extra Edge
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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**
```text
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.
Quick Answer: 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 originally formed a tree with nodes labeled from 1 to n. Exactly one additional edge was added between two different existing nodes, creating exactly one cycle.
Given the list of edges, return the edge that can be removed so the graph becomes a tree again.
If more than one edge could be removed, return the one that appears last in the input order.
Constraints
- n == len(edges)
- 3 <= n <= 1000
- 1 <= u, v <= n
- u != v
- The graph is connected and contains exactly one cycle
Examples
Input: ([[1, 2], [1, 3], [2, 3]],)
Expected Output: [2, 3]
Explanation: This is the smallest valid case. The third edge closes the cycle 1-2-3-1, so removing [2, 3] restores a tree.
Input: ([[1, 4], [1, 2], [2, 3], [3, 4]],)
Expected Output: [3, 4]
Explanation: All four edges are part of the cycle. Any of them could be removed, so we return the one that appears last in the input: [3, 4].
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.