# With explanation, Union find solution, python

• This problem took me a long time. And obviously here the defination of a tree is different from mine... In this problem, just consider it as an undirected graph, and to be a tree, there shouldn't be any loop. So our task is to cut the loop.

Then we can use union find to check if an edge will create a loop simply by checking if the two ends of the edge have the same root: `union.getRoot(edge[0]) == union.getRoot(edge[1])` . If not, we can assign the root of one end to be the root of the other end:`union.union[union.getRoot(edge[0])] = union.getRoot(edge[1])`

``````class Union(object):
def __init__(self):
self.union = {}
def getRoot(self, node):
if node not in self.union:
self.union[node] = node
while self.union[node] != node:
node = self.union[node]
return node
class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
union = Union()
for edge in edges:
if union.getRoot(edge[0]) == union.getRoot(edge[1]):
return edge
else:
union.union[union.getRoot(edge[0])] = union.getRoot(edge[1])
``````

• Thank you. Can you argue a bit on time & space complexity here? Also I suppose there is no path compression in this union-find data structure.

• Yes, I didn't do path compression here. The time complexity of `getRoot` in unionfind should be O(logn) on average, so total is O(mlogn), where m is the amount of edges and n is the amount of nodes, I guess. And space complexity should be O(n).

• My solution inspired by you and Stefan

Space complexity is O(1) - 2001 items in array
Time complexity - log(n) - where n is number of nodes in a tree

``````class UnionFind(object):
def __init__(self, size):
self.representative = [ i for i in range(size) ]

def find(self, node):
if self.representative[node] != node:
self.representative[node] = self.find(self.representative[node])
return self.representative[node]

def union(self, nodex, nodey):
self.representative[self.find(nodex)] = self.find(nodey)

class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""

union_find = UnionFind(2001)  # Since every integer represented in the 2D-array will be between 1 and 2000.

for u,v in edges:
if union_find.find(u) == union_find.find(v):
return [u,v]
union_find.union(u,v)
return []
``````

• @BigBiang without path compression I think find operation will be O(n).

• @sha256pki Actually I don't know how to determine the time complexity on average, I just saw this conclusion on wikipedia....The worst case should be O(n), but I am not sure about the complexity on average.

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