With explanation, Union find solution, python


  • 0

    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])
    

  • 0
    S

    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.


  • 0

    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).


  • 0
    S

    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 []
    

  • 0
    S

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


  • 0

    @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.


Log in to reply
 

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