Redundant Connection

Medium · Graphs

You are given a list of edges describing a graph that started as a tree on n nodes labeled 1 to n, then had exactly one extra edge added, creating a single cycle. Each edge is a pair of node labels, and the edges are given in the order they were added. Find the one edge that can be removed to turn the graph back into a tree; if more than one edge could work, return the one that appears last in the input list.

Examples

Input:  edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Why:    Nodes 1,2,3 already form a tree with edges [1,2] and [1,3]; adding [2,3] closes a cycle, so it is the redundant edge.

Input:  edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Why:    Edges [1,2],[2,3],[3,4] plus [1,5] already connect all 5 nodes as a tree, so [1,4] is the extra edge that creates the cycle.

Input:  edges = [[1,2],[1,3],[1,4],[3,4]]
Output: [3,4]
Why:    Nodes 1-4 are already connected via edges [1,2],[1,3],[1,4]; the edge [3,4] closes a cycle and is the last such edge, so it is removed.

Constraints

3 <= edges.length <= 1000, edges[i].length == 2, 1 <= edges[i][0], edges[i][1] <= edges.length, the input describes a tree with exactly one extra edge added and no self-loops

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Redundant Connection

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Redundant Connection. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.