algoadvance

Given a connected undirected graph with n nodes (labeled from 1 to n). You are tasked with finding an edge that, when removed, will result in a tree (that is, the graph will have no cycles). If there are multiple answers, return the edge that occurs last in the given input. The input edges are given as a 2D array edges where each element is a pair of nodes that form an edge in the graph.

Example 1:

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

Example 2:

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

Clarifying Questions

  1. What is the range of n?
    • The number of nodes n is between 3 and 1000.
  2. Are the edge pairs unique and do nodes have unique labels?
    • Yes, each edge appears only once in the input array, and nodes have unique labels within the range [1, n].
  3. Should we consider the edges directed?
    • No, the edges in this problem represent an undirected graph.

Strategy

To solve this problem, we’ll use the Union-Find (Disjoint Set) data structure to detect cycles in the graph. The Union-Find structure supports two main operations efficiently:

  1. Find: Determine which subset a particular element is in.
  2. Union: Join two subsets into a single subset.

If, while processing the edges, we find that adding an edge forms a cycle, this edge is the redundant one.

Here are the steps:

  1. Initialize the Union-Find structure.
  2. Process each edge one by one:
    • For each edge, use the “find” operation to check if the two nodes are in the same subset.
    • If they are in the same subset, the edge forms a cycle and is redundant.
    • If not, union the two subsets.
  3. Return the first edge that forms a cycle.

Code

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size
        
    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX != rootY:
            # Union by rank
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        else:
            return False

def findRedundantConnection(edges):
    n = len(edges)
    uf = UnionFind(n + 1)  # n+1 to handle 1-indexed nodes
    
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]

Time Complexity

Therefore, the overall time complexity of this solution is O(E), which is efficient given the constraints.

Try our interview co-pilot at AlgoAdvance.com