Redundant Connection

Medium

Union Find

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Union Find Approach:

Process edges one by one
For each edge (u, v), check if u and v are already in the same set
If they are already connected, this edge creates a cycle - it's redundant!
If not, union them

Key Insight: An edge is redundant if and only if it connects two nodes that are already in the same connected component.

Example 1

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

Output: [2,3]

Explanation: After adding edges [1,2] and [1,3], nodes 1,2,3 are connected. Edge [2,3] creates a cycle.

Example 2

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]

Output: [1,4]

Explanation: Edges [1,2], [2,3], [3,4] form a path. Edge [1,4] closes the cycle 1-2-3-4-1.

Constraints

•n == edges.length
•3 <= n <= 1000
•edges[i].length == 2
•1 <= ai < bi <= edges.length
•ai != bi
•There are no repeated edges.
•The given graph is connected.

Show Hints (4)

Hint 1: Process edges in order. For each edge, what question do you need to answer about the two endpoints?

Hint 2: An edge creates a cycle if and only if both endpoints are already connected. How can Union Find help detect this?

Hint 3: The find operation tells you which component a node belongs to. If find(a) == find(b), what does that mean for edge (a, b)?

Hint 4: Since you need to return the last redundant edge, process all edges but remember the last one that caused a cycle.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?