[C++/Python] DFS paint different colors, Union Find Solutions - with Picture - Clean & Concise
\u2714\uFE0F Solution 1: DFS - Paint different connected components by different colors\n- The idea is that we dfs to paint different connected components by di
**\u2714\uFE0F Solution 1: DFS - Paint different connected components by different colors**\n- The idea is that we `dfs` to paint different connected components by different colors, we gonna paint in-place on the `grid` matrix, so we start color from `2`, because `0` and `1` is already existed in the `grid`.\n- We need a counter, let `componentSize[color]` be the size of connected component corresponding to `color`.\n- Iterate over rows and columns in the matrix again, this time we calculate the new size that can be formed if we turn `matrix[r][c] from 0 into 1`, that is:\n\t- If `matrix[r][c] == 0` then:\n\t\t- Get color ids of landing neighboring cells to calculate component size. (We get unique color ids to avoid calculating the size of 2 connected component two times)\n\t\t- Calculate total size can be formed.\n\t\t- Update the largest size can be formed so far to our answer.\n\n![image](https://assets.leetcode.com/users/images/2292c663-4a43-47c5-a9bb-b88b148b152f_1627963871.547048.png)\n\n\n<iframe src="https://leetcode.com/playground/ehtZaxpn/shared" frameBorder="0" width="100%" height="710"></iframe>\n\n**Complexity**\n- Time: `O(M * N)`, where `M <= 500` is number of rows, `N <= 500` is number of columns in the matrix.\n- Space: `O(M * N)`\n\n---\n\n**\u2714\uFE0F Solution 2: Uninon-Find**\n- A **Union-Find** is a really good data structure to store the connected components with their respective sizes.\n- Iterate over rows and columns in the matrix, if a cell `matrix[r][c] == 1` then we connect that cell with its landing neighboring cells by using **Union-Find**.\n- Iterate over rows and columns in the matrix again, this time we calculate the new size that can be formed if we turn `matrix[r][c] from 0 into 1`, that is:\n\t- If `matrix[r][c] == 0` then:\n\t\t- Get unique parent ids of landing neighboring cells to calculate component size. (We get unique parent ids to avoid calculating the size of 2 connected component two times)\n\t\t- Calculate total size can be formed.\n\t\t- Update the largest size can be formed so far to our answer.\n- There is a simillar problem with this problem: [305. Number of Islands II](https://leetcode.com/problems/number-of-islands-ii/)\n```\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = [-1] * n\n        self.size = [0] * n\n    def isExist(self, u):\n        return self.parent[u] >= 0\n    def add(self, u):\n        if self.isExist(u): return  # Only add if not existed yet!\n        self.parent[u] = u\n        self.size[u] = 1\n    def find(self, u):\n        if self.parent[u] == u: return u\n        self.parent[u] = self.find(self.parent[u])  # Path compression\n        return self.parent[u]\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 the smaller component to the bigger component\n            self.parent[pu] = pv  # Merge u into v\n            self.size[pv] += self.size[pu]\n        else:\n            self.parent[pv] = pu  # Merge v into u\n            self.size[pu] += self.size[pv]\n        return True\n\nclass Solution:\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        DIR = [0, 1, 0, -1, 0]\n        m, n, ans = len(grid), len(grid[0]), 0\n        uf = UnionFind(m * n)\n\n        def landNeighbors(r, c):\n            for i in range(4):\n                nr, nc = r + DIR[i], c + DIR[i + 1]\n                neiId = nr * n + nc\n                if nr < 0 or nr == m or nc < 0 or nc == n or not uf.isExist(neiId): continue\n                yield neiId\n\n        for r in range(m):\n            for c in range(n):\n                if grid[r][c] == 0: continue\n                curId = r * n + c\n                uf.add(curId)\n                for neiId in landNeighbors(r, c):\n                    uf.union(curId, neiId)\n                p = uf.find(curId)\n                ans = max(ans, uf.size[p])\n\n        for r in range(m):\n            for c in range(n):\n                if grid[r][c] == 1: continue\n                neiParents = set()\n                for neiId in landNeighbors(r, c):\n                    neiParents.add(uf.find(neiId))\n                sizeFormed = 1  # Start with 1, which is matrix[r][c] when turning from 0 into 1\n                for p in neiParents:\n                    sizeFormed += uf.size[p]\n                ans = max(ans, sizeFormed)\n        return ans\n```\n**Complexity**\n- Time: `O(M * N * \u03B1(M*N)` ~ `O(M * N)`, where `M <= 500` is number of rows, `N <= 500` is number of columns in the matrix.\n\tExplanation: Using both **path compression** and **union by size** ensures that the **amortized time** per 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(M * N)`\n\nIf you think this **post is useful**, I\'m happy if you **give a vote**. Any **questions or discussions are welcome!** Thank a lot.
[]