Union Find with union by ranks and path compression
Time complexity: O(n2) because improved union find takes O(1) time and we traverse n * n grid, thus O(n * n * 1) = O(n2)\nSpace complexity: O(n) becuse UnionFin
Time complexity: O(n2) because improved union find takes O(1) time and we traverse n * n grid, thus O(n * n * 1) = O(n2)\nSpace complexity: O(n) becuse UnionFind allocates 2 arrays of n, thus O(n + n) = O(n)\n\n\tclass UnionFind:\n\t\tdef __init__(self, n):\n\t\t\tself.parents = [x for x in range(n)]\n\t\t\tself.count = [1 for _ in range(n)]\n\t\t\tself.groups = n\n\n\t\tdef find(self, a):\n\t\t\twhile a != self.parents[a]:\n\t\t\t\tself.parents[a] = self.parents[self.parents[a]]\n\t\t\t\ta = self.parents[a]\n\t\t\treturn a\n\n\t\tdef union(self, a, b):\n\t\t\ta_root, b_root = self.find(a), self.find(b)\n\n\t\t\tif a_root == b_root:\n\t\t\t\treturn True\n\n\t\t\tif self.count[a_root] > self.count[b_root]:\n\t\t\t\tself.parents[b_root] = a_root\n\t\t\t\tself.count[a_root] += self.count[b_root]\n\t\t\telse:\n\t\t\t\tself.parents[a_root] = b_root\n\t\t\t\tself.count[b_root] += self.count[a_root]\n\t\t\tself.groups -= 1\n\n\t\t\treturn False\n\n\tclass Solution:\n\t\tdef findCircleNum(self, grid: List[List[int]]) -> int:\n\t\t\tn = len(grid)\n\t\t\tif n < 1 or len(grid[0]) != n:\n\t\t\t\treturn 0\n\n\t\t\tunion = UnionFind(n)\n\n\t\t\tfor i in range(n):\n\t\t\t\tfor j in range(n):\n\t\t\t\t\tif grid[i][j] == 1:\n\t\t\t\t\t\tunion.union(i,j)\n\n\t\t\treturn union.groups
['Union Find', 'Python3']