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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Redundant Connection

Difficulty: Medium

Problem Description

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] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i 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.

Key Insights

  • The graph is originally a tree with n nodes and n-1 edges.
  • Adding one more edge creates exactly one cycle in the graph.
  • To find the redundant edge, we need to detect cycles in the graph.
  • The Union-Find (Disjoint Set Union) data structure is an efficient way to manage and detect cycles when adding edges.
  • If two vertices are already connected in the Union-Find structure, adding the edge creates a cycle.

Space and Time Complexity

Time Complexity: O(n α(n)), where α is the inverse Ackermann function, which grows very slowly and is nearly constant for practical input sizes. Space Complexity: O(n), for the parent and rank arrays in the Union-Find structure.

Solution

We can solve this problem using the Union-Find (Disjoint Set Union) approach. The idea is to maintain a set of connected components and process each edge one by one. For each edge, we check if the two vertices it connects are already in the same component. If they are, the edge is redundant (it creates a cycle). If they are not, we union the two components. We iterate through the edges and keep track of the last redundant edge found.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size
    
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]
    
    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU == rootV:
            return False  # They are already in the same component
        if self.rank[rootU] > self.rank[rootV]:
            self.parent[rootV] = rootU
        elif self.rank[rootU] < self.rank[rootV]:
            self.parent[rootU] = rootV
        else:
            self.parent[rootV] = rootU
            self.rank[rootU] += 1
        return True

def findRedundantConnection(edges):
    uf = UnionFind(len(edges) + 1)
    for edge in edges:
        if not uf.union(edge[0], edge[1]):
            return edge  # Found the redundant edge
← Back to All Questions