We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Redundant Connection II

Number: 685

Difficulty: Hard

Paid? No

Companies: Meta, Google

Problem Description

Given a directed graph that started as a rooted tree (with n nodes labeled from 1 to n) and then had one extra directed edge added, identify and remove exactly one edge so that the remaining graph is a rooted tree. A rooted tree has exactly one node (the root) with no parent and every other node has exactly one parent. The extra edge may cause either a cycle or a node having two parents. If multiple answers are possible, return the edge that appears last in the given list.

Key Insights

  • The extra edge introduces one of two issues:
    • A node has two parents.
    • A cycle exists in the graph.
  • First, scan through edges to detect if any node gets two parents. If found, there are two candidate edges.
  • Use the Union-Find data structure (Disjoint Set Union) to detect cycles.
  • Depending on whether a conflict (two parents) exists and/or a cycle is detected, decide which edge to remove:
    • If a node has two parents, test by ignoring the second candidate edge during union-find. If no cycle forms, the second candidate is removable; otherwise, remove the first candidate.
    • If no conflict exists, simply remove the edge that causes a cycle.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution consists of two main steps:

  1. Traverse the list of edges to detect whether any node has two parents. If such a node is found, mark the two candidate edges (candidate1: the earlier edge, candidate2: the later edge).
  2. Use the Union-Find algorithm to iterate over the edges:
    • If there is a conflict (i.e., a node with two parents), skip candidate2 initially.
    • While processing edges with Union-Find, check if adding an edge would create a cycle.
    • Finally, based on the presence of a cycle and the two-parent conflict, decide which candidate edge to return.

Key Data Structures:

  • An array (or hash map) to track the parent of each node.
  • The Union-Find (Disjoint Set Union) structure to union sets and detect cycles.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        candidate1 = None
        candidate2 = None
        # Dictionary to record the parent for each child node.
        childParent = {}
        # First pass: detect if a node has two parents.
        for u, v in edges:
            if v in childParent:
                candidate1 = [childParent[v], v]  # earlier edge providing parent
                candidate2 = [u, v]               # later edge providing parent
            else:
                childParent[v] = u
        
        # Initialize Union-Find structure: each node is its own parent.
        root = [i for i in range(n+1)]
        
        # Find function with path compression.
        def find(x):
            while root[x] != x:
                root[x] = root[root[x]]
                x = root[x]
            return x
        
        cycle_edge = None
        # Second pass: union-find to detect cycle, skip candidate2 if conflict exists.
        for u, v in edges:
            # If candidate2 exists and current edge is candidate2, skip it.
            if candidate2 and [u, v] == candidate2:
                continue
            parent_u = find(u)
            parent_v = find(v)
            # If they have the same root, a cycle is detected.
            if parent_u == parent_v:
                cycle_edge = [u, v]
            else:
                root[parent_v] = parent_u
        
        # Decide which edge to remove based on conflict and cycle detection.
        if candidate1:
            return candidate1 if cycle_edge else candidate2
        return cycle_edge
← Back to All Questions