python solution using union find
This question is similar to Number of Connected Components in an Undirected Graph\n\nsee this for union find explanation: https://youtu.be/ID00PMy0-vE\n\n\nclas
This question is similar to Number of Connected Components in an Undirected Graph\n\nsee this for union find explanation: https://youtu.be/ID00PMy0-vE\n\n```\nclass Solution(object):\n    def findCircleNum(self, M):\n        """\n        :type M: List[List[int]]\n        :rtype: int\n        """\n        ds = DisjointSet()\n\n        for i in range(len(M)):\n            ds.make_set(i)\n\n        for i in range(len(M)):\n            for j in range(len(M)):\n                if M[i][j] == 1:\n                    ds.union(i, j)\n\n        return ds.num_sets\n\nclass Node(object):\n    def __init__(self, data, parent=None, rank=0):\n        self.data = data\n        self.parent = parent\n        self.rank = rank\n\nclass DisjointSet(object):\n    def __init__(self):\n        self.map = {}\n        self.num_sets = 0\n\n    def make_set(self, data):\n        node = Node(data)\n        node.parent = node\n        self.map[data] = node\n        self.num_sets += 1\n\n    def union(self, data1, data2):\n        node1 = self.map[data1]\n        node2 = self.map[data2]\n\n        parent1 = self.find_set_util(node1)\n        parent2 = self.find_set_util(node2)\n\n        if parent1.data == parent2.data:\n            return\n\n        if parent1.rank >= parent2.rank:\n            if parent1.rank == parent2.rank:\n                parent1.rank += 1\n            parent2.parent = parent1\n        else:\n            parent1.parent = parent2\n\n        self.num_sets -= 1\n\n\n    def find_set(self, data):\n        return self.find_set_util(self.map[data])\n\n    def find_set_util(self, node):\n        parent = node.parent\n        if parent == node:\n            return parent\n\n        node.parent = self.find_set_util(node.parent) # path compression\n        return node.parent\n```
[]