<filename>union-find/union-by-rank.py
# https://leetcode.com/problems/redundant-connection/solution/

def findRedundantConnection(self, edges):
    parent = [0] * len(edges)

    def find(x):
      if parent[x] == 0:
        return x
      parent[x] = find(parent[x])
      return parent[x]
    
    def union(x, y):
      rootX = find(x)
      rootY = find(y)
      if rootX == rootY:
        return False
      parent[rootX] = rootY
      return True
      
    for x, y in edges:
      if not union(x - 1, y - 1): 
        return [x, y]
      
    raise ValueError("Illegal input.")
<filename>union-find/union-by-rank.py
# https://leetcode.com/problems/redundant-connection/solution/

def findRedundantConnection(self, edges):
    parent = [0] * len(edges)

    def find(x):
      if parent[x] == 0:
        return x
      parent[x] = find(parent[x])
      return parent[x]
    
    def union(x, y):
      rootX = find(x)
      rootY = find(y)
      if rootX == rootY:
        return False
      parent[rootX] = rootY
      return True
      
    for x, y in edges:
      if not union(x - 1, y - 1): 
        return [x, y]
      
    raise ValueError("Illegal input.")
# https://leetcode.com/problems/redundant-connection/solution/