[Python] Union Find Solution
Idea\n- Find connected components (island) and their size using Union Find\n- Iterate all 0s and check the adjacant 1s, if any, and which island it is adjacant 
**Idea**\n- Find connected components (island) and their size using Union Find\n- Iterate all 0s and check the adjacant 1s, if any, and which island it is adjacant to. \n- Sum the size of all adjacant islands and plus 1. It is the new connected area if the 0 is converted to 1.\n- update max area for each 0 in the grid. If no 0 in grid (all cells are 1s), return the size of grid.\n\n**Complexity**\n* Time: O(N^2)\n* Space: O(N^2)\n\t\t\n**Python**\n```\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        \n        # Union Find Solution\n        # Time: O(N^2)\n        # Space: O(N^2)\n        \n        N = len(grid)\n        \n        # union find and size of components\n        uf = {\n            (r, c): (r, c)\n            for r in range(N)\n            for c in range(N)\n            if grid[r][c]\n        }\n        \n        size = {\n            (r, c): 1\n            for r in range(N)\n            for c in range(N)\n            if grid[r][c]\n        }\n        \n        def find(x):\n            if x != uf[x]:\n                uf[x] = find(uf[x])\n            return uf[x]\n        \n        def union(x, y):\n            rootx = find(x)\n            rooty = find(y)\n            if rootx != rooty:\n                uf[rootx] = rooty\n                size[rooty] += size[rootx]\n            \n        # union adjacant 1s\n        for r in range(N):\n            for c in range(N):\n                if grid[r][c]:\n                    for nr, nc in [[r+1, c], [r, c+1]]:\n                        if 0 <= nr < N and 0 <= nc < N and grid[nr][nc]:\n                            union((r,c), (nr,nc))\n        \n        # iterate all 0s to find the max area\n        max_area = 0\n        has_zero = False\n        for r in range(N):\n            for c in range(N):\n                if grid[r][c] == 0:\n                    has_zero = True\n                    adj_islands = set()\n                    for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:\n                        if 0 <= nr < N and 0 <= nc < N and grid[nr][nc]:\n                            adj_islands.add(find((nr, nc)))\n                    area = 1 + sum(size[adj_island] for adj_island in adj_islands)\n                    max_area = max(max_area, area)\n                    \n        return max_area if has_zero else N * N\n```
['Union Find', 'Python']