Python union-find code


  • 0
    J
    class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        root = [i for i in range(n)]
        s = set()
        for edge in edges:
            self.union(edge[0], edge[1], root)
        for i in range(n):
            s.add(self.find(i, root))
        return len(s)
        
    def find(self, i, root):
        if root[i] == i:
            return i
        root[i] = self.find(root[i], root)
        return root[i]
    def union(self, i, j, root):
        root[self.find(i, root)] = self.find(j, root)

Log in to reply
 

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