<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 getEdges(self, grid, node, visited, islandId, mode='traverse'):
#         directionList = [(-1, 0), (0, 1), (1, 0), (0, -1)]
#         xlim, ylim = len(grid[0]), len(grid)
#         edgeList = []
#         for direc in directionList:
#             newX, newY = node[0] + direc[0], node[1] + direc[1]
#             if ((0 <= newX < xlim) and 
#                 (0 <= newY < ylim) and 
#                 (grid[newY][newX] == 1)):
#                 if ((mode == 'traverse') and
#                     (visited[newY][newX] == 0)):
#                     edgeList.append((newX, newY))
#                     visited[newY][newX] = islandId
#                 elif (mode == 'merge'):
#                     edgeList.append(visited[newY][newX])
#         return(edgeList)
        
#     def traverse(self, grid, node, visited, islandId):
#         area = 1
#         for edge in self.getEdges(grid, node, visited, islandId):
#             area += self.traverse(grid, edge, visited, islandId)
#         return(area)
            
#     def searchForIslands(self, grid):
#         visited = [[0] * len(grid[0]) for _ in range(len(grid))]
#         islandId = 1
#         islandAreaDict = {}
#         for idxX in range(len(grid[0])):
#             for idxY in range(len(grid)):
#                 if ((grid[idxY][idxX] == 1) and
#                     (visited[idxY][idxX] == 0)):
#                     visited[idxY][idxX] = islandId
#                     thisArea = self.traverse(grid, (idxX, idxY), visited, islandId)
#                     islandAreaDict[islandId] = thisArea
#                     islandId += 1        
#         return(visited, 
#                islandAreaDict)
    
#     def largestIsland(self, grid: List[List[int]]) -> int:
#         visited, islandAreaDict = self.searchForIslands(grid)
#         maxArea = max(islandAreaDict.values()) if islandAreaDict else 0
#         for idxX in range(len(grid[0])):
#             for idxY in range(len(grid)):
#                 if (grid[idxY][idxX] == 0):
#                     thisArea = 1
#                     for edgeId in set(self.getEdges(grid, (idxX, idxY), visited, 0, 'merge')):
#                         thisArea += islandAreaDict[edgeId]
#                     maxArea = max(maxArea, thisArea)
#         return(maxArea)
    

# class Solution:
#     def getEdges(self, grid, node, visited, islandId, mode='traverse'):
#         directionList = [(-1, 0), (0, 1), (1, 0), (0, -1)]
#         xlim, ylim = len(grid[0]), len(grid)
#         edgeList = []
#         for direc in directionList:
#             newX, newY = node[0] + direc[0], node[1] + direc[1]
#             if ((0 <= newX < xlim) and
#                 (0 <= newY < ylim) and
#                 (grid[newY][newX] == 1)):
#                 if ((mode == 'traverse') and 
#                     (visited[newY][newX] == 0)):
#                     edgeList.append((newX, newY))
#                     visited[newY][newX] = islandId
#                 elif mode == 'merge':
#                     edgeList.append(visited[newY][newX])
#         return(edgeList)
            
#     def traverse(self, grid, node, visited, islandId):
#         nodeQueue = deque([node])
#         area = 0
#         while nodeQueue:
#             node = nodeQueue.popleft()
#             area += 1
#             for edge in self.getEdges(grid, node, visited, islandId):
#                 nodeQueue.append(edge)
#         return(area)
        
#     def searchForIslands(self, grid):
#         visited = [[0] * len(grid[0]) for _ in range(len(grid))]
#         islandAreaDict = {}
#         islandId = 1
#         for idxX in range(len(grid[0])):
#             for idxY in range(len(grid)):
#                 if ((grid[idxY][idxX] == 1) and
#                     (visited[idxY][idxX] == 0)):
#                     visited[idxY][idxX] = islandId
#                     islandAreaDict[islandId] = self.traverse(grid, (idxX, idxY), visited, islandId)
#                     islandId += 1
#         return(visited,
#                islandAreaDict)

#     def largestIsland(self, grid: List[List[int]]) -> int:
#         visited, islandAreaDict = self.searchForIslands(grid)
#         maxArea = max(islandAreaDict.values()) if islandAreaDict else 0
#         for idxX in range(len(grid[0])):
#             for idxY in range(len(grid)):
#                 if grid[idxY][idxX] == 0:
#                     thisArea = 1
#                     for edgeId in set(self.getEdges(grid, (idxX, idxY), visited, 0, 'merge')):
#                         thisArea += islandAreaDict[edgeId]
#                     maxArea = max(maxArea, thisArea)
#         return(maxArea)    


class Solution:    
    def getEdges(self, grid, node):
        directionList = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        xlim, ylim = len(grid[0]), len(grid)
        edgeList = []
        for direc in directionList:
            newX, newY = node[0] + direc[0], node[1] + direc[1]
            if ((0 <= newX < xlim) and
                (0 <= newY < ylim) and
                (grid[newY][newX] == 1)):
                edgeList.append((newX, newY))
        return(edgeList)
        
    def find(self, graphMatrix, node):
        if graphMatrix[node[1]][node[0]][0] != node:
            graphMatrix[node[1]][node[0]] = self.find(graphMatrix, graphMatrix[node[1]][node[0]][0])
        return(graphMatrix[node[1]][node[0]])
        
    def union(self, graphMatrix, node0, node1):
        ancestor0, size0 = self.find(graphMatrix, node0)
        ancestor1, size1 = self.find(graphMatrix, node1)
        if ancestor0 == ancestor1:
            return(graphMatrix[node0[1]][node0[0]])
        if size0 < size1:
            ancestor0, size0, ancestor1, size1 = ancestor1, size1, ancestor0, size0
        graphMatrix[ancestor0[1]][ancestor0[0]] = (ancestor0, size0 + size1)
        graphMatrix[ancestor1[1]][ancestor1[0]] = graphMatrix[ancestor0[1]][ancestor0[0]]
        return(graphMatrix[node0[1]][node0[0]])
        
    def constructGraph(self, grid):
        graphMatrix = [[((idxX, idxY), 1) for idxX in range(len(grid[0]))]
                       for idxY in range(len(grid))]
        for idxX in range(len(grid[0])):
            for idxY in range(len(grid)):
                if grid[idxY][idxX] == 1:
                    for edge in self.getEdges(grid, (idxX, idxY)):
                        self.union(graphMatrix, (idxX, idxY), edge)
        return(graphMatrix)
        
    def getMaxArea(self, grid):
        graphMatrix = self.constructGraph(grid)
        maxArea = 0
        for idxX in range(len(grid[0])):
            for idxY in range(len(grid)):
                if grid[idxY][idxX] == 0:
                    thisArea = 1
                    for edge in set(self.find(graphMatrix, x)[0] 
                                    for x in self.getEdges(grid, (idxX, idxY))):
                        thisArea += self.find(graphMatrix, edge)[1]
                    maxArea = max(maxArea, thisArea)
        return(maxArea if maxArea != 0 else len(grid[0]) * len(grid))
        
    def largestIsland(self, grid: List[List[int]]) -> int:
        return(self.getMaxArea(grid))
58881