#685

Hard

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Redundant Connection II

Find and remove the redundant connection in a directed graph that was originally a rooted tree.

depth first search breadth first search union find graph

Problem Statement

You are given a directed graph with n nodes. Initially, the graph is a rooted tree, but one additional directed edge has been added. The graph contains exactly one cycle, and you need to find the redundant connection that causes this cycle and return it. The graph is represented by a 2D array, where each element [u, v] indicates a directed edge from node u to node v.

Your task is to identify and return the redundant connection. Since there is exactly one redundant edge, you can safely assume that the input graph is guaranteed to contain one and only one cycle. The problem should be solved using graph traversal techniques such as DFS or BFS.

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],[4,1],[1,5]]

Output: [4,1]

Example details omitted.

Constraints

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n
ui != vi

Solution Approach

DFS for Cycle Detection

Use depth-first search (DFS) to traverse the graph. As you visit nodes, keep track of the visited nodes to detect cycles. Once a cycle is detected, the last edge added to the cycle is the redundant connection.

Union-Find (Disjoint Set) for Efficient Tracking

Union-Find is another efficient approach for cycle detection. As you iterate through the edges, union the nodes. If two nodes are already in the same set, the current edge is redundant and causes the cycle.

BFS for Detecting Redundant Edges

Breadth-first search (BFS) can also be applied to find the redundant connection. Traverse the graph level by level, tracking visited nodes. If a node is visited again, it indicates the cycle and the edge leading to it is redundant.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity for both DFS and Union-Find approaches is O(N), where N is the number of nodes. The space complexity is also O(N) due to the storage required for tracking visited nodes and sets in Union-Find.

What Interviewers Usually Probe

The candidate uses an efficient cycle detection algorithm like DFS or Union-Find.
The candidate is able to explain the graph traversal approach clearly and apply it correctly.
The candidate identifies and removes the redundant edge without unnecessary computation.

Common Pitfalls or Variants

Common pitfalls

Not properly tracking the visited nodes, leading to incorrect cycle detection.
Confusing Union-Find operations, such as not correctly implementing union and find operations.
Failing to handle edge cases where the graph has only a single redundant connection.

Follow-up variants

Graph with multiple redundant edges (not allowed in this problem but can be extended to handle).
Using BFS instead of DFS for traversal and cycle detection.
Handling larger graphs with optimizations in both space and time complexity.

FAQ

How do I detect the redundant edge in a directed graph?

Use depth-first search or Union-Find to detect the cycle caused by the redundant edge. The last edge that completes the cycle is the redundant one.

Can BFS be used to solve the Redundant Connection II problem?

Yes, BFS can be used for cycle detection by traversing the graph level by level and identifying the first revisited node, which forms the cycle.

What are the main patterns used to solve Redundant Connection II?

Graph traversal techniques, specifically DFS, BFS, and Union-Find, are the main patterns used to detect the redundant connection.

What is the time complexity of solving Redundant Connection II?

The time complexity is O(N), where N is the number of nodes, for both DFS and Union-Find approaches.

How does GhostInterview help with solving Redundant Connection II?

GhostInterview provides step-by-step explanations of graph traversal techniques, helping you detect cycles and find the redundant edge with ease.

terminal

Solution

Solution 1: Union-Find

According to the problem description, for a rooted tree, the in-degree of the root node is $0$, and the in-degree of other nodes is $1$. After adding an edge to the tree, there can be the following three scenarios:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

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

        n = len(edges)
        ind = [0] * n
        for _, v in edges:
            ind[v - 1] += 1
        dup = [i for i, (_, v) in enumerate(edges) if ind[v - 1] == 2]
        p = list(range(n))
        if dup:
            for i, (u, v) in enumerate(edges):
                if i == dup[1]:
                    continue
                pu, pv = find(u - 1), find(v - 1)
                if pu == pv:
                    return edges[dup[0]]
                p[pu] = pv
            return edges[dup[1]]
        for i, (u, v) in enumerate(edges):
            pu, pv = find(u - 1), find(v - 1)
            if pu == pv:
                return edges[i]
            p[pu] = pv

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

14

15

16

17

18

19

20

21

22

23

24

25

26

27

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

        n = len(edges)
        ind = [0] * n
        for _, v in edges:
            ind[v - 1] += 1
        dup = [i for i, (_, v) in enumerate(edges) if ind[v - 1] == 2]
        p = list(range(n))
        if dup:
            for i, (u, v) in enumerate(edges):
                if i == dup[1]:
                    continue
                pu, pv = find(u - 1), find(v - 1)
                if pu == pv:
                    return edges[dup[0]]
                p[pu] = pv
            return edges[dup[1]]
        for i, (u, v) in enumerate(edges):
            pu, pv = find(u - 1), find(v - 1)
            if pu == pv:
                return edges[i]
            p[pu] = pv

Continue Practicing

#684 redundant connection #765 couples holding hands #785 is graph bipartite