• We essentially want to find all the edges that form a cycle and return the last one. Below is my code using union find.

You can find very clear explanation of union find algo in this link: https://youtu.be/ID00PMy0-vE

This question is very similar to finding cycle in undirected graph using union find

``````class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
ds = DisjointSet()
result = []

for u, v in edges:
ds.make_set(u)
ds.make_set(v)

for u, v in edges:
parent1 = ds.find_set(u)
parent2 = ds.find_set(v)

if parent1 == parent2: # cycle, add to result list
result.append([u, v])
else:
ds.union(u, v)

return result[-1]

class Node(object):
def __init__(self, data, parent = None, rank = 0):
self.data = data
self.parent = parent
self.rank = rank

def __str__(self):
return str(self.data)

def __repr__(self):
return self.__str__()

class DisjointSet(object):
def __init__(self):
self.map = {}
self.num_sets = 0

def make_set(self, data):
node = Node(data)
node.parent = node # very important!
self.map[data] = node
self.num_sets += 1 # make_set increases the number of disjoint sets by one

def union(self, data1, data2):
# gets nodes given data values
node1 = self.map[data1]
node2 = self.map[data2]

# get parents given nodes
parent1 = self.find_set_util(node1)
parent2 = self.find_set_util(node2)

# if they are part of same set do nothing
if parent1.data == parent2.data:
return

# else whoever's rank is higher becomes parent of other
if parent1.rank >= parent2.rank:
# increment rank only if both sets have same rank
if parent1.rank == parent2.rank:
parent1.rank = parent1.rank + 1
parent2.parent = parent1
else:
parent1.parent = parent2

self.num_sets -= 1 # union decreases the number of disjoint sets by one

# Finds the representative of this set
def find_set(self, data):
return self.find_set_util(self.map[data]) # pass in the node

# Find the representative recursively and does path compression as well.
def find_set_util(self, node):
parent = node.parent
if parent == node:
return parent

node.parent = self.find_set_util(node.parent) # path compression
return node.parent
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.