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

Number: 684

Difficulty: Medium

Paid? No

Companies: Google, Meta, Bloomberg, InMobi, Microsoft, Amazon, TikTok

Problem Description

Given an undirected graph that started as a tree (connected and acyclic) with n nodes labeled from 1 to n, an extra edge was added to the tree resulting in exactly one cycle. The task is to detect and return the redundant edge that, when removed, will restore the tree property. If multiple such edges exist, return the one that appears last in the input.

Key Insights

  • The problem can be solved using a Union Find (Disjoint Set Union) data structure.
  • As we iterate over each edge, we check whether the two vertices are already connected.
  • If connecting the two vertices would create a cycle (i.e., they already belong to the same set), then the current edge is redundant.
  • Alternatives like DFS or BFS are possible, but Union Find offers a more straightforward and efficient solution.

Space and Time Complexity

Time Complexity: O(n * α(n)) where α(n) is the inverse Ackermann function (almost constant in practice). Space Complexity: O(n), for storing the parent array used in the Union Find structure.

Solution

We use the Union Find algorithm by maintaining an array where each node points to its parent. For each edge, we perform a find operation on both endpoints:

  • If the endpoints belong to the same set, adding this edge would create a cycle and it is marked as redundant.
  • Otherwise, we union the two sets. This algorithm efficiently detects the extra edge that introduces a cycle in the graph.

Code Solutions

# Python solution using Union Find with path compression.

class UnionFind:
    def __init__(self, size):
        # Initialize parent pointers for each node.
        self.parent = list(range(size))
    
    def find(self, x):
        # Find the root of x with path compression.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union the sets of x and y.
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False  # Cycle detected.
        self.parent[rootY] = rootX
        return True

def findRedundantConnection(edges):
    # Number of nodes is equal to len(edges) because edges were from a tree.
    n = len(edges)
    uf = UnionFind(n + 1)  # Account for node labels starting at 1.
    redundant_edge = None
    for edge in edges:
        a, b = edge
        # If union returns False, a cycle is detected.
        if not uf.union(a, b):
            redundant_edge = edge
    return redundant_edge

# Example usage:
edges = [[1,2],[1,3],[2,3]]
print(findRedundantConnection(edges))  # Output: [2, 3]
← Back to All Questions