<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 Node:
    def __init__(self):
        self.parent = self
        self.size = 1

class UnionFind:
    def find(self, node):
        if node.parent != node:
            node.parent = self.find(node.parent)
        return node.parent
    
    def union(self, node1, node2):
        p1 = self.find(node1)
        p2 = self.find(node2)
        if p1 != p2:
            if p1.size >= p2.size:
                p2.parent = p1
                p1.size += p2.size
                
            else:
                p1.parent = p2
                p2.size += p1.size
                



class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        m = len(grid)
        n = len(grid[0])
        nodes = {}
        uf = UnionFind()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    if (i,j) not in nodes:
                        cur = Node()
                        nodes[(i,j)] = cur
                       
                    if i + 1 < m and grid[i+1][j] == 1:
                        if (i+1, j) not in nodes:
                            node_d = Node()
                            nodes[(i+1, j)] = node_d
                        uf.union(nodes[(i,j)], nodes[(i+1, j)])

                    if j + 1 < n and grid[i][j+1] == 1:
                        if (i, j+1) not in nodes:
                            node_r = Node()
                            nodes[(i, j+1)] = node_r
                        uf.union(nodes[(i,j)], nodes[(i, j+1)])

        max_size = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    cur_size = 1
                    seen = set()
                    if i - 1 >= 0 and grid[i-1][j] == 1:
                        cur_size += uf.find(nodes[(i-1, j)]).size
                        parent_1 = uf.find(nodes[(i-1, j)])
                        seen.add(parent_1)
                    if j - 1 >= 0 and grid[i][j-1] == 1:
                        parent_2 = uf.find(nodes[(i, j-1)])
                        if parent_2 not in seen:
                            cur_size += uf.find(nodes[(i, j-1)]).size
                            seen.add(parent_2)
                    if i + 1 < m and grid[i+1][j] == 1:
                        parent_3 = uf.find(nodes[(i+1, j)])
                        if parent_3  not in seen:
                            cur_size += uf.find(nodes[(i+1, j)]).size
                            seen.add(parent_3)
                    if j + 1 < n and grid[i][j+1] == 1:
                        parent_4 = uf.find(nodes[(i, j+1)])
                        if parent_4 not in seen:
                            cur_size += uf.find(nodes[(i, j+1)]).size
                    max_size = max(max_size, cur_size)
        if max_size == 0:
            max_size = uf.find(nodes[(0,0)]).size
        return max_size


53893