[Python Union Find] The most standard template for Union Find
\n# We have 3 method to write Union Find. \n# 1, by Brute force,\n# 2, by size,\n# 3, by rank (depth).\n\nThe template of them is below.\n\n# 1, written by brut
```\n# We have 3 method to write Union Find. \n# 1, by Brute force,\n# 2, by size,\n# 3, by rank (depth).\n```\nThe template of them is below.\n```\n# 1, written by brute force:\nclass UF:\n\n\tdef __init__(self, n):\n\t\tself.parent = {i: i for i in range(n)}\n\t\n\tdef find(self, x):\n\t\tif x != self.parent[x]:\n\t\t\tself.parent[x] = self.find(self.parent[x])\n\t\treturn self.parent[x]\n\t\n\tdef union(self, x, y):\n\t\tself.parent[self.find(x)] = self.find(y)\n```\n```\n# 2, written by size:\nclass UF:\n\n\tdef __init__(self, n):\n\t\tself.parent = {i: i for i in range(n)}\n\t\tself.size = {i: 1 for i in range(n)}\n\t\n\tdef find(self, x):\n\t\tif x != self.parent[x]:\n\t\t\tself.parent[x] = self.find(self.parent[x])\n\t\treturn self.parent[x]\n\t\n\tdef union(self, x, y):\n\t\trootX = self.find(x)\n\t\trootY = self.find(y)\n\t\tif rootX == rootY:\n\t\t\treturn\n\t\t\n\t\tif self.size[rootX] <= self.size[rootY]:\n\t\t\tself.parent[rootX] = rootY\n\t\t\tself.size[rootY] += self.size[rootX]\n\t\t\n\t\telse:\n\t\t\tself.parent[rootY] = rootX\n\t\t\tself.size[rootX] += self.size[rootY]\n```\n```\n# 3, written by rank (depth):\nclass UF:\n\n\tdef __init__(self, n):\n\t\tself.parent = {i: i for i in range(n)}\n\t\tself.rank = {i: 1 for i in range(n)}\n\t\n\tdef find(self, x):\n\t\tif x != self.parent[x]:\n\t\t\tself.parent[x] = self.find(self.parent[x])\n\t\treturn self.parent[x]\n\t\n\tdef union(self, x, y):\n\t\trootX = self.find(x)\n\t\trootY = self.find(y)\n\t\tif rootX == rootY:\n\t\t\treturn\n\t\t\n\t\tif self.rank[rootX] < self.rank[rootY]:\n\t\t\tself.parent[rootX] = rootY\n\t\t\n\t\telif self.rank[rootY] < self.rank[rootX]:\n\t\t\tself.parent[rootY] = rootX\n\t\t\n\t\telse:\n\t\t\tself.parent[rootX] = rootY\n\t\t\tself.rank[rootY] += 1\n```\n\n```\n# The answer below is the type written by size.\n# We have another 2 writing methods, that is, written by Brute force and written by rank (depth).\n# Size is the common one that we usually write, but it can not deal with some particular cases.\n# For example, \n"""\n        1            4\n2   3   0              5\n                         6\n                   \nWe can see the right tree has depth 3, left has depth 2. So\nit is better to combine in this way, that is, put left tree into right tree, then the depth is still 3.\n\n            4\n\t      1    5\n 2    3   0      6\n\t \nBut if we write by size, since left size is 4, right size is 3, left > right, \nso we put right tree into left, then the left tree increase the depth, which is not good.\n\n            1\n\t2   3   0   4\n                   5\n\t\t\t\t      6\n\nBut writing Union Find in size way will give you the benefit when the problem wants you to count\nthe total number of nodes in the tree. Usually we write in the way of size.\n\nThis problem of course can be written in Brute force way, but that is too brute.\n"""\n```\n```\nclass UF:\n    \n    def __init__(self, n):\n        self.parent = {i: i for i in range(n)}\n        self.size = {i: 1 for i in range(n)}\n    \n    def find(self, x):\n        if x != self.parent[x]:\n            self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n    \n    def union(self, x, y):\n        rootX = self.find(x)\n        rootY = self.find(y)\n        if rootX == rootY:\n            return\n        \n        if self.size[rootX] <= self.size[rootY]:\n            self.parent[rootX] = rootY\n            self.size[rootY] += self.size[rootX]\n        \n        else: \n            self.parent[rootY] = rootX\n            self.size[rootX] += self.size[rootY]\n    \n    def find_max(self):\n        return max(self.size.values())\n\n    \nclass Solution:\n    def longestConsecutive(self, nums: List[int]) -> int:\n        \n        if not nums:\n            return 0\n        \n        n = len(nums)\n        \n        uf = UF(n)\n        \n        dic = {}\n        \n        for i in range(n):\n            \n            if nums[i] in dic:\n                continue\n            \n            dic[nums[i]] = i\n            \n            if nums[i] + 1 in dic:\n                uf.union(i, dic[nums[i] + 1])\n            \n            if nums[i] - 1 in dic:\n                uf.union(i, dic[nums[i] - 1])\n        \n        return uf.find_max()\n```
['Union Find', 'Python']