[Python] Union Find - Clean & Concise
\u2714\uFE0F Solution 1: Union Find (Naive)\npython\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = [i for i in range(n)]\n        \n    de
**\u2714\uFE0F Solution 1: Union Find (Naive)**\n```python\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = [i for i in range(n)]\n        \n    def find(self, u):\n        if u != self.parent[u]:\n            u = self.find(self.parent[u])\n        return u\n    \n    def union(self, u, v):\n        pu, pv = self.find(u), self.find(v)\n        if pu == pv: return False\n        self.parent[pu] = pv\n        return True\n\nclass Solution:\n    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n        n = len(isConnected)\n        \n        component = n\n        uf = UnionFind(n)\n        for i in range(n):\n            for j in range(i+1, n):\n                if isConnected[i][j] == 1 and uf.union(i, j):\n                    component -= 1\n        return component\n```\nComplexity:\n- Time: `O(N^3)`, where `N <= 200` is number of nodes\n- Space: `O(N)`\n\n---\n**\u2714\uFE0F Solution 2: Union Find (Path Compression)**\n```python\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = [i for i in range(n)]\n        \n    def find(self, u):\n        if u != self.parent[u]:\n            self.parent[u] = self.find(self.parent[u])  # Path compression\n        return self.parent[u]\n    \n    def union(self, u, v):\n        pu, pv = self.find(u), self.find(v)\n        if pu == pv: return False\n        self.parent[pu] = pv\n        return True\n\nclass Solution:\n    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n        n = len(isConnected)\n        \n        component = n\n        uf = UnionFind(n)\n        for i in range(n):\n            for j in range(i+1, n):\n                if isConnected[i][j] == 1 and uf.union(i, j):\n                    component -= 1\n        return component\n```\nComplexity:\n- Time: `O(N^2 * logN)`, where `N <= 200` is number of nodes\n- Space: `O(N)`\n\n---\n**\u2714\uFE0F Solution 3: Union Find (Union by Size & Path Compression)**\n```python\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = [i for i in range(n)]\n        self.size = [1] * n\n        \n    def find(self, u):\n        if u != self.parent[u]:\n            self.parent[u] = self.find(self.parent[u])  # Path compression\n        return self.parent[u]\n    \n    def union(self, u, v):\n        pu, pv = self.find(u), self.find(v)\n        if pu == pv: return False\n        if self.size[pu] < self.size[pv]:  # Merge pu to pv\n            self.size[pv] += self.size[pu]\n            self.parent[pu] = pv\n        else:\n            self.size[pu] += self.size[pv]\n            self.parent[pv] = pu\n        return True\n\n\nclass Solution:\n    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n        n = len(isConnected)\n        \n        component = n\n        uf = UnionFind(n)\n        for i in range(n):\n            for j in range(i+1, n):\n                if isConnected[i][j] == 1 and uf.union(i, j):\n                    component -= 1\n        return component\n```\nComplexity:\n- Time: `O(N^2 * \u03B1(N))` ~ `O(N^2)`, where `N <= 200` is number of nodes\n   Explanation: Using both **path compression** and **union by size** ensures that the **amortized time** per **UnionFind** operation is only `\u03B1(n)`, which is optimal, where `\u03B1(n)` is the inverse Ackermann function. This function has a value `\u03B1(n) < 5` for any value of n that can be written in this physical universe, so the disjoint-set operations take place in essentially constant time.\nReference: https://en.wikipedia.org/wiki/Disjoint-set_data_structure or https://www.slideshare.net/WeiLi73/time-complexity-of-union-find-55858534 for more information.\n- Space: `O(N)`
[]