<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:
        '''
        identify all islands and associate each the island id
        go over all zeros, fetch neighbouring islands and combine their sizes
        if no zeros, return the size of the grid
        '''
        def adj(i, j):
            return [
                (x, y) for x, y in
                [(i, j+1), (i, j-1), (i-1,j), (i+1,j)]
                if 0 <= x < self.n and 0 <= y < self.n and grid[x][y] and (x, y) not in self.seen
            ]
        def dfs(x):
            queue = [x]
            count = 0
            while queue:
                cur = queue.pop()
                if cur in self.seen:
                    continue
                self.seen[cur] = x
                count += 1
                nodes = adj(*cur)
                queue.extend(nodes)
            self.counts[x] = count

        self.seen = {}
        self.counts = {}
        zeros = []
        self.n = len(grid)
        for i in range(self.n):
            for j in range(self.n):
                if grid[i][j] and (i, j) not in self.seen:
                    dfs((i, j))
                elif grid[i][j] == 0:
                    zeros.append((i, j))
        visited = self.seen
        self.seen = {}
        largest = 0
        print(self.counts)
        if zeros:
            for i, j in zeros:
                cur = sum(self.counts[y] for y in set(visited[x] for x in adj(i, j))) + 1
                if cur > largest:
                    largest = cur
        else:
            largest = self.n ** 2
        return largest

51756