<p>You are given an <code>n x n</code> binary matrix <code>grid</code>. You are allowed to change <strong>at most one</strong> <code>0</code> to be <code>1</code>.</p>

<p>Return <em>the size of the largest <strong>island</strong> in</em> <code>grid</code> <em>after applying this operation</em>.</p>

<p>An <strong>island</strong> is a 4-directionally connected group of <code>1</code>s.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0],[0,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,0]]
<strong>Output:</strong> 4
<strong>Explanation: </strong>Change the 0 to 1 and make the island bigger, only one island with area = 4.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Can&#39;t change any 0 to 1, only one island with area = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        found = False
        for i in range(len(grid)):
            for j in range(len(grid)):
                if not grid[i][j] or found:
                    found = True
                    break
        if not found:
            return len(grid)*len(grid)

        parent = []
        for i in range(len(grid)):
            row = []
            for j in range(len(grid[0])):
                row.append((i, j))
            parent.append(row)
        
        size = [[grid[j][i] for i in range(len(grid))] for j in range(len(grid))]
        def get_parent(parent_cp, r, c):
            if (r, c) == parent_cp[r][c]:
                return (r, c)
            parent_cp[r][c] = get_parent(parent_cp, parent_cp[r][c][0], parent_cp[r][c][1])
            return parent_cp[r][c]

        def union_by_size(parent_cp, size, u, v):
            parent_u = get_parent(parent_cp, u[0], u[1])
            parent_v = get_parent(parent_cp, v[0], v[1])

            if parent_u == parent_v:
                return False
            
            if size[parent_u[0]][parent_u[1]] > size[parent_v[0]][parent_v[1]]:
                parent_cp[parent_v[0]][parent_v[1]] = parent_u
                size[parent_u[0]][parent_u[1]] += size[parent_v[0]][parent_v[1]]
            else:
                parent_cp[parent_u[0]][parent_u[1]] = parent_v
                size[parent_v[0]][parent_v[1]] += size[parent_u[0]][parent_u[1]]
            
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid)):
                if grid[i][j]:
                    for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                        new_row = i + dr
                        new_col = j + dc
                        if new_row < 0 or new_col < 0 or new_row >= len(grid) or new_col >= len(grid) or not grid[new_row][new_col]:
                            continue
                        else:
                            union_by_size(parent, size, (i, j), (new_row, new_col))
                else:
                    count += 1
        
        if count == len(grid) * len(grid):
            return 1
        
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid)):
                tmp = 1
                parent_visited = set()
                if not grid[i][j]:
                    for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                        new_row = i + dr
                        new_col = j + dc
                        if new_row < 0 or new_col < 0 or new_row >= len(grid) or new_col >= len(grid) or not grid[new_row][new_col] or get_parent(parent, new_row, new_col) in parent_visited:
                            continue
                        parent_row, parent_col = get_parent(parent, new_row, new_col)
                        parent_visited.add((parent_row, parent_col))
                        tmp += size[parent_row][parent_col]
                    res = max(res, tmp)
                        
        return res
43206