#684

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Redundant Connection

Identify and remove the redundant edge that causes a cycle in a graph starting as a tree.

depth first search breadth first search union find graph

Problem Statement

You are given a graph that started as a tree with n nodes, labeled from 1 to n, with one extra edge added. This added edge creates a cycle in the graph. You need to determine which edge can be removed so that the resulting graph becomes a tree, eliminating the cycle. If there are multiple possible answers, return the one that appears last in the input.

The graph is represented by an array of edges, where edges[i] = [ai, bi] indicates an edge between nodes ai and bi. The graph is connected, and there are no repeated edges. Your task is to find and remove the redundant edge that forms the cycle, restoring the graph to its tree structure.

Examples

Example 1

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

Output: [2,3]

Example details omitted.

Example 2

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

Output: [1,4]

Example details omitted.

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.

Solution Approach

Graph Traversal with Depth-First Search (DFS)

Using DFS, traverse the graph while keeping track of visited nodes. When you encounter a node that has already been visited, it indicates a cycle. The last edge forming this cycle is the redundant one.

Union Find (Disjoint Set Union)

With Union Find, iterate over the edges and perform union operations. If two nodes are already in the same set, the current edge is redundant and forms a cycle. The last such edge encountered is the redundant edge.

Breadth-First Search (BFS)

A BFS approach can also be used to find cycles by level-order traversal. Track the parent of each node during traversal. If an edge leads to an already visited node that isn’t the parent, it forms a cycle.

Complexity Analysis

Metric	Value
Time	O(N \cdot \alpha(N))
Space	O(N)

The time complexity is O(N * α(N)), where N is the number of nodes, and α(N) is the inverse Ackermann function. The space complexity is O(N) due to the storage needed for the graph and visited nodes.

What Interviewers Usually Probe

Look for the candidate's ability to efficiently detect cycles in a graph using DFS or Union Find.
Assess how well the candidate explains the significance of the cycle and redundant edge removal.
Evaluate their understanding of graph traversal and cycle detection trade-offs.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the tree structure and treating the graph as fully connected without considering the cycle.
Not recognizing the last added edge as the answer when multiple redundant edges exist.
Incorrectly applying DFS or Union Find without careful tracking of visited nodes or sets.

Follow-up variants

Handle graphs with multiple cycles and determine which cycle's edge to remove.
Implement the solution using BFS instead of DFS or Union Find.
Extend the problem to handle undirected graphs with weighted edges.

FAQ

What is the approach to solve the Redundant Connection problem?

The problem can be solved using Depth-First Search (DFS), Union Find, or Breadth-First Search (BFS). Each technique helps to detect cycles and identify the redundant edge.

How do you detect cycles in a graph for Redundant Connection?

You can detect cycles using DFS or Union Find by checking if an edge connects two already visited or unified nodes.

What should be returned if there are multiple redundant edges?

If multiple redundant edges are found, return the one that appears last in the input list.

What is the time complexity of the Redundant Connection problem?

The time complexity is O(N * α(N)), where N is the number of nodes, and α(N) is the inverse Ackermann function.

How does Union Find help in solving the Redundant Connection problem?

Union Find helps by efficiently tracking connected components. If two nodes are already in the same component, the current edge forms a cycle and is redundant.

terminal

Solution

Solution 1: Union-Find

According to the problem description, we need to find an edge that can be removed so that the remaining part is a tree with $n$ nodes. We can traverse each edge and determine whether the two nodes of this edge are in the same connected component. If they are in the same connected component, it means this edge is redundant and can be removed, so we directly return this edge. Otherwise, we merge the two nodes connected by this edge into the same connected component.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(len(edges)))
        for a, b in edges:
            pa, pb = find(a - 1), find(b - 1)
            if pa == pb:
                return [a, b]
            p[pa] = pb

Solution 2: Union-Find (Template Approach)

Here is a template approach using Union-Find for your reference.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(len(edges)))
        for a, b in edges:
            pa, pb = find(a - 1), find(b - 1)
            if pa == pb:
                return [a, b]
            p[pa] = pb

Continue Practicing

#685 redundant connection ii #765 couples holding hands #785 is graph bipartite