python solution using union find

  • 3

    This question is similar to Number of Connected Components in an Undirected Graph

    see this for union find explanation:

    class Solution(object):
        def findCircleNum(self, M):
            :type M: List[List[int]]
            :rtype: int
            ds = DisjointSet()
            for i in range(len(M)):
            for i in range(len(M)):
                for j in range(len(M)):
                    if M[i][j] == 1:
                        ds.union(i, j)
            return ds.num_sets
    class Node(object):
        def __init__(self, data, parent=None, rank=0):
   = data
            self.parent = parent
            self.rank = rank
    class DisjointSet(object):
        def __init__(self):
   = {}
            self.num_sets = 0
        def make_set(self, data):
            node = Node(data)
            node.parent = node
  [data] = node
            self.num_sets += 1
        def union(self, data1, data2):
            node1 =[data1]
            node2 =[data2]
            parent1 = self.find_set_util(node1)
            parent2 = self.find_set_util(node2)
            if ==
            if parent1.rank >= parent2.rank:
                if parent1.rank == parent2.rank:
                    parent1.rank += 1
                parent2.parent = parent1
                parent1.parent = parent2
            self.num_sets -= 1
        def find_set(self, data):
            return self.find_set_util([data])
        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

Log in to reply

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