In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).
Example 1:
Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:
Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
 
Notes:

1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal

Spanning trees

Starter code: class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		for i in range(len(grid)):
			grid[i].insert(0, 0)
			grid[i].append(0)
		grid.insert(0, [0 for i in range(len(grid[0]))])
		grid.append([0 for i in range(len(grid[0]))])
		islands = []
		max_length = 1
		for i in range(1, len(grid) - 1):
			for j in range(1, len(grid[0]) - 1):
				if grid[i][j] != 1:
					continue
				island_id = len(islands)
				length = 0
				connect_length = 0
				queue = [(i, j)]
				grid[i][j] = 2 + island_id
				while queue:
					(x, y) = queue.pop()
					for (dx, dy) in directions:
						this_grid = grid[x + dx][y + dy]
						if this_grid == 1:
							grid[x + dx][y + dy] = 2 + island_id
							queue.append((x + dx, y + dy))
						elif isinstance(this_grid, list):
							new_connect = 0
							already = False
							for old_island_id in this_grid:
								if old_island_id != island_id:
									new_connect += islands[old_island_id]
								else:
									already = True
							if not already:
								connect_length = max(connect_length, new_connect)
								this_grid.append(island_id)
						else:
							grid[x + dx][y + dy] = [island_id]
					length += 1
				islands.append(length)
				max_length = max(max_length, length + connect_length + 1)
		return min(max_length, (len(grid) - 2) * (len(grid[0]) - 2))


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		n_rows = len(grid)
		n_cols = len(grid[0])
		borders = dict()
		seen = set()
		max_size = 0

		def bfs(r, c):
			nonlocal max_size
			size = 1
			border = set()
			stack = [(r, c)]
			while stack:
				(r, c) = stack.pop()
				for (r, c) in [(r + 1, c), (r - 1, c), (r, c - 1), (r, c + 1)]:
					if 0 <= r < n_rows and 0 <= c < n_cols and ((r, c) not in seen):
						if grid[r][c] == 1:
							size += 1
							stack.append((r, c))
							seen.add((r, c))
						else:
							border.add((r, c))
			max_size = max(max_size, size)
			for (r, c) in border:
				if (r, c) in borders:
					max_size = max(max_size, borders[r, c] + size)
					borders[r, c] = borders[r, c] + size
				else:
					borders[r, c] = size
		for r in range(n_rows):
			for c in range(n_cols):
				if grid[r][c] == 1 and (r, c) not in seen:
					seen.add((r, c))
					bfs(r, c)
		return max_size + 1 if max_size != n_rows * n_cols else max_size


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		nei = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		(m, n) = (len(grid), len(grid[0]))
		rec = dict()
		ans = 0

		def count(grid, i, j):
			cnt = 1
			grid[i][j] = -1
			for (dx, dy) in nei:
				(nx, ny) = (i + dx, j + dy)
				if 0 <= nx < m and 0 <= ny < n and (grid[nx][ny] == 1):
					cnt += count(grid, nx, ny)
			return cnt

		def flip(grid, i, j, val):
			grid[i][j] = val
			for (dx, dy) in nei:
				(nx, ny) = (i + dx, j + dy)
				if 0 <= nx < m and 0 <= ny < n and (grid[nx][ny] == -1):
					flip(grid, nx, ny, val)
			return
		color = 2
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					temp = count(grid, i, j)
					flip(grid, i, j, color)
					rec[color] = temp
					color += 1
					ans = max(ans, temp)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 0:
					visit = set()
					for (dx, dy) in nei:
						(nx, ny) = (i + dx, j + dy)
						if 0 <= nx < m and 0 <= ny < n and (grid[nx][ny] != 0):
							visit.add(grid[nx][ny])
					ans = max(ans, 1 + sum((rec[i] for i in visit)))
		return ans


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		if not grid or not grid[0]:
			return 0
		(m, n) = (len(grid), len(grid[0]))
		islandId = 2
		areaDict = {}
		maxArea = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					areaDict[islandId] = self.dfs(grid, i, j, m, n, islandId)
					maxArea = max(maxArea, areaDict[islandId])
					islandId += 1
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 0:
					neighborIslands = set()
					for (ni, nj) in self.getNeighbors(grid, i, j, m, n):
						if grid[ni][nj] > 0:
							neighborIslands.add(grid[ni][nj])
					maxArea = max(maxArea, 1 + sum([areaDict[islandId] for islandId in neighborIslands]))
		return maxArea

	def dfs(self, grid, i, j, m, n, islandId):
		area = 1
		grid[i][j] = islandId
		for (ni, nj) in self.getNeighbors(grid, i, j, m, n):
			if grid[ni][nj] != 1:
				continue
			area += self.dfs(grid, ni, nj, m, n, islandId)
		return area

	def bfs(self, grid, i, j, m, n, islandId):
		grid[i][j] = islandId
		area = 1
		q = [(i, j)]
		while q:
			(x, y) = q.pop(0)
			for (nx, ny) in self.getNeighbors(grid, x, y, m, n):
				if grid[nx][ny] != 1:
					continue
				area += 1
				grid[nx][ny] = islandId
				q.append((nx, ny))
		return area

	def getNeighbors(self, grid, x, y, m, n):
		result = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
		return [(a, b) for (a, b) in result if 0 <= a < m and 0 <= b < n and (grid[a][b] > 0)]


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:

		def neighbors(r, c):
			for (nr, nc) in [(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)]:
				if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
					yield (nr, nc)

		def dfs(r, c, island_num):
			island_area = 1
			grid[r][c] = island_num
			for (nr, nc) in neighbors(r, c):
				if grid[nr][nc] == 1:
					island_area += dfs(nr, nc, island_num)
			return island_area
		area = {}
		island_num = 2
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] == 1:
					area[island_num] = dfs(r, c, island_num)
					island_num += 1
		ans = max(area.values() or [0])
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] == 0:
					neighboring_islands = set()
					for (nr, nc) in neighbors(r, c):
						if grid[nr][nc] > 1:
							neighboring_islands.add(grid[nr][nc])
					ans = max(ans, 1 + sum((area[i] for i in neighboring_islands)))
		return ans


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def move(i, j):
			for (x, y) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
				if 0 <= i + x < m and 0 <= j + y < n:
					yield (i + x, j + y)

		def dfs(i, j, key):
			res = 0
			grid[i][j] = key
			for (x, y) in move(i, j):
				if grid[x][y] == 1:
					res += dfs(x, y, key)
			return res + 1
		mappings = {0: 0}
		index = 2
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					mappings[index] = dfs(i, j, index)
					index += 1
		res = max(mappings.values())
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 0:
					temp = set((grid[x][y] for (x, y) in move(i, j)))
					res = max(res, sum((mappings[key] for key in temp)) + 1)
		return res


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		u = {(r, c): (r, c) for (r, row) in enumerate(grid) for (c, v) in enumerate(row) if v}

		def head(p):
			if u[p] == p:
				return p
			u[p] = head(u[p])
			return u[p]
		for (r, row) in enumerate(grid):
			for (c, v) in enumerate(row):
				if not v:
					continue
				for (nr, nc) in [(r - 1, c), (r, c - 1)]:
					if nr < 0 or nc < 0 or (not grid[nr][nc]):
						continue
					u[head((r, c))] = head((nr, nc))
		islands = {p: 0 for (p, h) in list(u.items()) if p == h}
		for p in u:
			islands[head(p)] += 1
		max_size = max(list(islands.values()), default=0)
		for (r, row) in enumerate(grid):
			for (c, v) in enumerate(row):
				if v:
					continue
				connected = set()
				for (nr, nc) in [(r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)]:
					if nr < 0 or nc < 0 or nr >= len(grid) or (nc >= len(row)) or (not grid[nr][nc]):
						continue
					if (nr, nc) in u:
						connected.add(head((nr, nc)))
				size = 1 + sum((islands[i] for i in connected))
				max_size = max(max_size, size)
		return max_size


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		(nrows, ncols) = (len(grid), len(grid[0]))
		dp = [[(0, 0) for _ in range(ncols)] for _ in range(nrows)]
		cum_visited = set()
		isl_no = 1
		maxsize = 0
		for r in range(nrows):
			for c in range(ncols):
				if (r, c) not in cum_visited and grid[r][c] == 1:
					visited = set()
					self.dfs(grid, r, c, visited)
					size = len(visited)
					maxsize = max(maxsize, size)
					for (x, y) in visited:
						dp[x][y] = (isl_no, size)
					cum_visited = cum_visited.union(visited)
					isl_no += 1
		for r in range(nrows):
			for c in range(ncols):
				if grid[r][c] == 0:
					sz = self.join_zero(grid, dp, r, c)
					maxsize = max(maxsize, sz)
		return maxsize

	def join_zero(self, grid, dp, r, c):
		islands = set()
		for (nr, nc) in [(r - 1, c), (r, c - 1), (r, c + 1), (r + 1, c)]:
			if nr >= 0 and nr < len(grid) and (nc >= 0) and (nc < len(grid[0])) and (dp[nr][nc][1] != 0):
				islands.add(dp[nr][nc])
		if len(islands) == 0:
			return 1
		return sum((x[1] for x in islands)) + 1

	def dfs(self, grid, r, c, visited):
		visited.add((r, c))
		for (n_r, n_c) in [(r - 1, c), (r, c - 1), (r, c + 1), (r + 1, c)]:
			if n_r >= 0 and n_r < len(grid) and (n_c >= 0) and (n_c < len(grid[0])) and (grid[n_r][n_c] == 1) and ((n_r, n_c) not in visited):
				self.dfs(grid, n_r, n_c, visited)


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:

		def markIsland(grid, pos, root, d):
			i = pos[0]
			j = pos[1]
			if pos in d.get(root, set()):
				return
			if root not in d:
				d[root] = set()
			d[root].add(pos)
			if i > 0 and grid[i - 1][j] == 1:
				markIsland(grid, (i - 1, j), root, d)
			if i < len(grid) - 1 and grid[i + 1][j] == 1:
				markIsland(grid, (i + 1, j), root, d)
			if j > 0 and grid[i][j - 1] == 1:
				markIsland(grid, (i, j - 1), root, d)
			if j < len(grid[i]) - 1 and grid[i][j + 1] == 1:
				markIsland(grid, (i, j + 1), root, d)
			if pos == root:
				for entry in d[root]:
					grid[entry[0]][entry[1]] = len(d[root])
			return

		def checkBranch(grid, pos, pos_dict, checked):

			def getSurrounding(grid, pos, pos_dict, checked):
				if pos in checked:
					return checked[pos]
				visited = set()
				i = pos[0]
				j = pos[1]
				ret = 1
				if i > 0 and grid[i - 1][j] != 0 and (pos_dict[i - 1, j] not in visited):
					visited.add(pos_dict[i - 1, j])
					ret += grid[i - 1][j]
				if i < len(grid) - 1 and grid[i + 1][j] != 0 and (pos_dict[i + 1, j] not in visited):
					visited.add(pos_dict[i + 1, j])
					ret += grid[i + 1][j]
				if j > 0 and grid[i][j - 1] != 0 and (pos_dict[i, j - 1] not in visited):
					visited.add(pos_dict[i, j - 1])
					ret += grid[i][j - 1]
				if j < len(grid[i]) - 1 and grid[i][j + 1] != 0 and (pos_dict[i, j + 1] not in visited):
					visited.add(pos_dict[i, j + 1])
					ret += grid[i][j + 1]
				checked[pos] = ret
				return ret
			i = pos[0]
			j = pos[1]
			max_connect = 1
			if i > 0 and grid[i - 1][j] == 0:
				max_connect = max(max_connect, getSurrounding(grid, (i - 1, j), pos_dict, checked))
			if i < len(grid) - 1 and grid[i + 1][j] == 0:
				max_connect = max(max_connect, getSurrounding(grid, (i + 1, j), pos_dict, checked))
			if j > 0 and grid[i][j - 1] == 0:
				max_connect = max(max_connect, getSurrounding(grid, (i, j - 1), pos_dict, checked))
			if j < len(grid[i]) - 1 and grid[i][j + 1] == 0:
				max_connect = max(max_connect, getSurrounding(grid, (i, j + 1), pos_dict, checked))
			return max_connect
		d = dict()
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if grid[i][j] == 1:
					markIsland(grid, (i, j), (i, j), d)
		max_size = 1
		pos_dict = dict()
		for (key, value) in d.items():
			max_size = max(max_size, len(value))
			for pos in value:
				pos_dict[pos] = key
		checked = dict()
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				max_size = max(max_size, checkBranch(grid, (i, j), pos_dict, checked))
		return max_size


class UF:

	def __init__(self, grid):
		N = len(grid[0]) * len(grid)
		self.parent = list(range(N))
		self.size = [0] * N
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j]:
					self.size[i * len(grid) + j] = 1

	def find(self, a):
		if self.parent[a] != a:
			self.parent[a] = self.find(self.parent[a])
			self.parent[a] = self.parent[self.parent[a]]
		return self.parent[a]

	def union(self, a, b):
		(pa, pb) = (self.find(a), self.find(b))
		if pa != pb:
			self.parent[pa] = pb
			self.size[pb] += self.size[pa]

class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		if not grid or not grid[0]:
			return 0
		uf = UF(grid)
		(N, M) = (len(grid), len(grid[0]))
		for i in range(N):
			for j in range(M):
				if not grid[i][j]:
					continue
				for (dx, dy) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
					(nx, ny) = (i + dx, j + dy)
					if 0 <= nx < N and 0 <= ny < M and grid[nx][ny]:
						uf.union(i * N + j, nx * N + ny)
		mx = 0
		for i in range(N):
			for j in range(M):
				if grid[i][j]:
					continue
				all_adjacent = 0
				seen = set()
				for (dx, dy) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
					(nx, ny) = (i + dx, j + dy)
					if 0 <= nx < N and 0 <= ny < M and grid[nx][ny]:
						parent = uf.find(nx * N + ny)
						if parent not in seen:
							seen.add(parent)
							all_adjacent += uf.size[parent]
				mx = max(mx, 1 + all_adjacent)
		return max(mx, max(uf.size))


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		(ROW, COL) = (len(grid), len(grid[0]))
		labels = [[0] * COL for _ in range(ROW)]
		id = 0

		def neighbors(r, c):
			for (nr, nc) in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
				if nr >= 0 and nr < ROW and (nc >= 0) and (nc < COL):
					yield (nr, nc)

		def dfs(row, col, id):
			if row < 0 or row >= ROW or col < 0 or (col >= COL):
				return
			if labels[row][col] > 0 or grid[row][col] == 0:
				return
			labels[row][col] = id
			for (nr, nc) in neighbors(row, col):
				dfs(nr, nc, id)
		for row in range(ROW):
			for col in range(COL):
				if grid[row][col] == 1:
					id += 1
					dfs(row, col, id)
		size = collections.defaultdict(int)
		for row in range(ROW):
			for col in range(COL):
				id = labels[row][col]
				if id > 0:
					size[id] += 1
		ans = max(list(size.values()) or [0])
		for row in range(ROW):
			for col in range(COL):
				if grid[row][col] == 1:
					continue
				seen = {labels[nr][nc] for (nr, nc) in neighbors(row, col) if grid[nr][nc] == 1}
				ans = max(ans, 1 + sum([size[id] for id in seen]))
		return ans


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		island_sizes = {}
		(max_island_id, max_island_size) = (-1, 0)
		global_island_id = 2
		zeros = set()
		deltas = ((1, 0), (-1, 0), (0, 1), (0, -1))
		(rows, cols) = (len(grid), len(grid[0]))

		def dfs(row, col, island_id) -> int:
			if row < 0 or row >= rows or col < 0 or (col >= cols) or (grid[row][col] != 1):
				return 0
			count = 1
			grid[row][col] = island_id
			for (dr, dc) in deltas:
				count += dfs(row + dr, col + dc, island_id)
			return count
		for (r, row) in enumerate(grid):
			for (c, val) in enumerate(row):
				if val == 1:
					cur_size = dfs(r, c, global_island_id)
					island_sizes[global_island_id] = cur_size
					if cur_size > max_island_size:
						max_island_size = cur_size
						max_island_id = global_island_id
					global_island_id += 1
				elif val == 0:
					zeros.add((r, c))
		if not zeros:
			return max_island_size
		for (r, c) in zeros:
			cur_max_size = 1
			islands_seen = set()
			for (dr, dc) in deltas:
				(nr, nc) = (r + dr, c + dc)
				if 0 <= nr < rows and 0 <= nc < cols:
					cur_val = grid[nr][nc]
					if cur_val in island_sizes and cur_val not in islands_seen:
						islands_seen.add(cur_val)
						cur_max_size += island_sizes[cur_val]
			max_island_size = max(max_island_size, cur_max_size)
		return max_island_size


class DSU:

	def __init__(self, N):
		self.par = [i for i in range(N)]
		self.cnt = N

	def find(self, i):
		if self.par[i] != i:
			self.par[i] = self.find(self.par[i])
		return self.par[i]

	def union(self, i, j):
		pi = self.find(i)
		pj = self.find(j)
		if pi != pj:
			self.par[pi] = pj
			self.cnt -= 1

class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		R = len(grid)
		C = len(grid[0])
		dsu = DSU(R * C)
		dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
		for y in range(R):
			for x in range(C):
				if grid[y][x] == 1:
					for (dx, dy) in dirs:
						(nx, ny) = (dx + x, dy + y)
						if 0 <= nx < C and 0 <= ny < R and (grid[ny][nx] == 1):
							dsu.union(y * R + x, ny * R + nx)
		smap = {}
		for y in range(R):
			for x in range(C):
				if grid[y][x] == 1:
					r = dsu.find(y * R + x)
					if r in smap:
						smap[r] += 1
					else:
						smap[r] = 1
		ans = 0
		for y in range(R):
			for x in range(C):
				if grid[y][x] == 0:
					rset = set()
					for (dx, dy) in dirs:
						(nx, ny) = (dx + x, dy + y)
						if 0 <= nx < C and 0 <= ny < R and (grid[ny][nx] == 1):
							r = dsu.find(ny * R + nx)
							rset.add(r)
					t = 1
					for r in rset:
						t += smap[r]
					ans = max(ans, t)
		return ans if ans != 0 else R * C


class UnionFind:

	def __init__(self, N):
		self.parents = [i for i in range(N)]
		self.size = [1] * N

	def find(self, x):
		root = x
		while root != self.parents[root]:
			root = self.parents[root]
		while x != root:
			parent = self.parents[x]
			self.parents[x] = root
			x = parent
		return root

	def union(self, a, b):
		root_a = self.find(a)
		root_b = self.find(b)
		if root_a == root_b:
			return False
		if self.size[root_a] <= self.size[root_b]:
			self.parents[root_a] = root_b
			self.size[root_b] += self.size[root_a]
		else:
			self.parents[root_b] = root_a
			self.size[root_a] += self.size[root_b]
		return True

class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def rc2idx(r, c):
			return r * n + c
		uf = UnionFind(m * n)
		max_area = 0
		for r in range(m):
			for c in range(n):
				if grid[r][c] == 1:
					for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
						(nr, nc) = (r + dr, c + dc)
						if not (0 <= nr < m and 0 <= nc < n):
							continue
						if grid[nr][nc] == 1:
							uf.union(rc2idx(r, c), rc2idx(nr, nc))
					max_area = max(max_area, uf.size[uf.find(rc2idx(r, c))])
		for r in range(m):
			for c in range(n):
				area = 0
				if grid[r][c] == 0:
					area = 1
					unique_neis = set()
					for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
						(nr, nc) = (r + dr, c + dc)
						if not (0 <= nr < m and 0 <= nc < n):
							continue
						if grid[nr][nc] == 1:
							island = uf.find(rc2idx(nr, nc))
							unique_neis.add(island)
					area += sum([uf.size[island] for island in unique_neis])
				max_area = max(max_area, area)
		return max_area


class UnionFind:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [1] * n

	def find(self, x):
		root = x
		while self.parent[root] != root:
			root = self.parent[root]
		while x != root:
			tmp = self.parent[x]
			self.parent[x] = root
			x = tmp
		return root

	def union(self, a, b):
		root_a = self.find(a)
		root_b = self.find(b)
		if root_a == root_b:
			return False
		if self.size[root_a] <= self.size[root_b]:
			self.parent[root_a] = root_b
			self.size[root_b] += self.size[root_a]
		else:
			self.parent[root_b] = root_a
			self.size[root_a] += self.size[root_b]
		return True

class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		m = len(grid)
		n = len(grid[0])
		uf = UnionFind(m * n)
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] == 0:
					continue
				rc = r * m + c
				for (r_off, c_off) in directions:
					(new_r, new_c) = (r + r_off, c + c_off)
					if not (0 <= new_r < len(grid) and 0 <= new_c < len(grid[0])):
						continue
					if grid[new_r][new_c] == 1:
						new_rc = new_r * m + new_c
						uf.union(rc, new_rc)
		max_area = max(uf.size)
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] == 1:
					continue
				rc = r * m + c
				neighbours = set()
				for (r_off, c_off) in directions:
					(new_r, new_c) = (r + r_off, c + c_off)
					if not (0 <= new_r < len(grid) and 0 <= new_c < len(grid[0])):
						continue
					if grid[new_r][new_c] == 1:
						new_rc = new_r * m + new_c
						neighbours.add(uf.find(new_rc))
				max_area = max(max_area, 1 + sum([uf.size[i] for i in neighbours]))
		return max_area


class Solution(object):

	def largestIsland(self, grid):
		N = len(grid)

		def neighbors(r, c):
			for (nr, nc) in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
				if 0 <= nr < N and 0 <= nc < N:
					yield (nr, nc)

		def dfs(r, c, index):
			ans = 1
			grid[r][c] = index
			for (nr, nc) in neighbors(r, c):
				if grid[nr][nc] == 1:
					ans += dfs(nr, nc, index)
			return ans
		area = {}
		index = 2
		for r in range(N):
			for c in range(N):
				if grid[r][c] == 1:
					area[index] = dfs(r, c, index)
					index += 1
		ans = max(area.values() or [0])
		for r in range(N):
			for c in range(N):
				if grid[r][c] == 0:
					seen = {grid[nr][nc] for (nr, nc) in neighbors(r, c) if grid[nr][nc] > 1}
					ans = max(ans, 1 + sum((area[i] for i in seen)))
		return ans


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		ret = 1
		size = []
		direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		h = len(grid)
		w = len(grid[0])

		def dfs(y0, x0, mark):
			if grid[y0][x0] == 1:
				grid[y0][x0] = mark
			inc = 0
			cnt = 0
			seen = []
			for (y_offset, x_offset) in direction:
				y1 = y0 + y_offset
				x1 = x0 + x_offset
				if 0 <= x1 < w and 0 <= y1 < h:
					if grid[y0][x0] == 0 and grid[y1][x1] < 0 and (grid[y1][x1] != mark) and (grid[y1][x1] not in seen):
						seen.append(grid[y1][x1])
						inc += size[-grid[y1][x1] - 1]
					elif grid[y0][x0] == mark and grid[y1][x1] >= 0:
						(a, b) = dfs(y1, x1, mark)
						cnt += a
						inc = max(inc, b)
			print((cnt + (0 if grid[y0][x0] == 0 else 1), inc + (1 if grid[y0][x0] == 0 else 0)))
			return (cnt + (0 if grid[y0][x0] == 0 else 1), inc + (1 if grid[y0][x0] == 0 else 0))
		idx = -1
		for y in range(h):
			for x in range(w):
				if grid[y][x] == 1:
					(cnt, inc) = dfs(y, x, idx)
					size.append(cnt)
					ret = max(ret, cnt + inc)
					idx -= 1
		return ret


from collections import defaultdict, Counter

class Solution:

	def find(self, j):
		if self.d[j] == j:
			return j
		self.d[j] = self.find(self.d[j])
		return self.d[j]

	def union(self, ij1, ij2):
		i1 = self.find(ij1)
		i2 = self.find(ij2)
		if i1 == i2:
			return
		if self.rank[i2] > self.rank[i1]:
			self.d[i1] = i2
		else:
			if self.rank[i1] >= self.rank[i2]:
				self.d[i2] = i1
			self.rank[i1] += 1

	def largestIsland(self, grid: List[List[int]]) -> int:
		(self.rank, self.d) = ({}, {})
		self.z = []
		self.res = 1
		for (r, row) in enumerate(grid):
			for (c, col) in enumerate(row):
				if col == 1:
					self.d[r, c] = (r, c)
					self.rank[r, c] = 0
				if col == 0:
					self.z.append((r, c))
		for (a, b) in list(self.d.keys()):
			search = [(a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)]
			for (c, d) in search:
				if 0 <= c < len(grid) and 0 <= d < len(grid[0]) and (grid[c][d] == 1):
					self.union((a, b), (c, d))
		for key in list(self.d.keys()):
			self.find(key)
		cc = Counter(list(self.d.values()))
		if cc:
			self.res = max(cc.values())
		for (a, b) in self.z:
			search = [(a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)]
			total = {}
			for (c, d) in search:
				if 0 <= c < len(grid) and 0 <= d < len(grid[0]) and (grid[c][d] == 1):
					(e, f) = self.d[c, d]
					total[e, f] = cc[e, f]
			print(('total ', total))
			s = sum(total.values())
			self.res = max(self.res, s + 1)
		return self.res


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		R = len(grid)
		C = len(grid[0])
		label = 2
		sum_of_area = 0
		max_area = 0
		map_info = {}
		for i in range(R):
			for j in range(C):
				if grid[i][j] == 1:
					area = self.findIsland(grid, i, j, R, C, label)
					map_info[label] = area
					sum_of_area += area
					label += 1
		print(map_info)
		print(grid)
		for i in range(R):
			for j in range(C):
				if grid[i][j] == 0:
					current = self.testChange(grid, i, j, R, C, map_info)
					if current > max_area:
						max_area = current
		if max_area == 0:
			max_area = sum_of_area
		return max_area

	def testChange(self, grid_info, i, j, R, C, map_info):
		island = []
		area = 0
		if 0 <= i + 1 < R and grid_info[i + 1][j] > 0:
			island.append(grid_info[i + 1][j])
		if 0 <= i - 1 < R and grid_info[i - 1][j] > 0:
			island.append(grid_info[i - 1][j])
		if 0 <= j + 1 < C and grid_info[i][j + 1] > 0:
			island.append(grid_info[i][j + 1])
		if 0 <= j - 1 < C and grid_info[i][j - 1] > 0:
			island.append(grid_info[i][j - 1])
		if not island:
			return 1
		for key in list(map_info.keys()):
			if key in island:
				area += map_info[key]
		return area + 1

	def findIsland(self, grid, i, j, R, C, label):
		area = 0
		if (i >= R or j >= C or i < 0 or (j < 0)) or grid[i][j] == 0 or grid[i][j] == label:
			return 0
		else:
			area = grid[i][j]
			grid[i][j] = label
		return area + self.findIsland(grid, i, j + 1, R, C, label) + self.findIsland(grid, i, j - 1, R, C, label) + self.findIsland(grid, i + 1, j, R, C, label) + self.findIsland(grid, i - 1, j, R, C, label)


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		(N, M) = (len(grid), len(grid[0]))
		visited = [[0] * M for _ in range(N)]
		group_ids_ = collections.defaultdict()
		group_counts_ = collections.Counter()
		_id_ = 0
		previous_count = 0
		for row in range(N):
			for col in range(M):
				if grid[row][col] == 1 and visited[row][col] == 0:
					_id_ += 1
					visited[row][col] = 1
					stack = [(row, col)]
					group_ids_[row, col] = _id_
					while stack:
						(r, c) = stack.pop()
						for (newr, newc) in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
							if 0 <= newr < N and 0 <= newc < M and (visited[newr][newc] == 0) and (grid[newr][newc] == 1):
								visited[newr][newc] = 1
								stack.append((newr, newc))
								group_ids_[newr, newc] = _id_
					group_counts_[_id_] = sum([sum(l) for l in visited]) - previous_count
					previous_count = sum([sum(l) for l in visited])
		biggest = 0
		hasZero = False
		for r in range(N):
			for c in range(M):
				if grid[r][c] == 0:
					hasZero = True
					groups = set()
					for (newr, newc) in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
						if 0 <= newr < N and 0 <= newc < M and (grid[newr][newc] == 1):
							groups.add(group_ids_[newr, newc])
					biggest = max(biggest, sum([group_counts_[_id_] for _id_ in groups]) + 1)
		if hasZero:
			return biggest
		else:
			return N * M


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:

		def method1():
			R = len(grid)
			if R < 1:
				return 0
			C = len(grid[0])

			def neighbors(r, c):
				for (dr, dc) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					(nr, nc) = (r + dr, c + dc)
					if 0 <= nr < R and 0 <= nc < C:
						yield (nr, nc)

			def dfs(r, c, visited):
				if (r, c) in seen:
					return
				if grid[r][c] == 0:
					return
				seen.add((r, c))
				visited.add((r, c))
				for (nr, nc) in neighbors(r, c):
					dfs(nr, nc, visited)
			ans = float('-inf')
			seen = set()
			cc = []
			zeros = set()
			for r in range(R):
				for c in range(C):
					if grid[r][c] == 1 and (r, c) not in seen:
						visited = set()
						dfs(r, c, visited)
						if visited:
							cc.append(visited)
					if grid[r][c] == 0:
						zeros.add((r, c))
			if len(zeros) == R * C:
				return 1
			ans = len(max(cc, key=len))
			for (r, c) in zeros:
				nei = {(nr, nc) for (nr, nc) in neighbors(r, c)}
				if len(cc) == 1:
					if any(((r, c) in cc[0] for (r, c) in nei)):
						ans = max(ans, len(cc[0]) + 1)
				else:
					for i in range(len(cc)):
						for j in range(i, len(cc)):
							if i != j and any(((r, c) in cc[i] for (r, c) in nei)) and any(((r, c) in cc[j] for (r, c) in nei)):
								ans = max(ans, len(cc[i]) + len(cc[j]) + 1)
			return ans

		def method2():
			R = len(grid)
			if R < 1:
				return 0
			C = len(grid[0])

			def neighbors(r, c):
				for (dr, dc) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					(nr, nc) = (r + dr, c + dc)
					if 0 <= nr < R and 0 <= nc < C:
						yield (nr, nc)

			def dfs(r, c, index):
				ans = 1
				grid[r][c] = index
				for (nr, nc) in neighbors(r, c):
					if grid[nr][nc] == 1:
						ans += dfs(nr, nc, index)
				return ans
			area = {}
			index = 2
			for r in range(R):
				for c in range(C):
					if grid[r][c] == 1:
						area[index] = dfs(r, c, index)
						index += 1
			ans = max(list(area.values()) or [0])
			for r in range(R):
				for c in range(C):
					if grid[r][c] == 0:
						seen = {grid[nr][nc] for (nr, nc) in neighbors(r, c) if grid[nr][nc] > 1}
						ans = max(ans, 1 + sum((area[i] for i in seen)))
			return ans
		return method2()


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

		def dfs(row, col, index):
			if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[0])) or (grid[row][col] != 1):
				return 0
			grid[row][col] = index
			area = 1
			for direction in directions:
				area += dfs(row + direction[0], col + direction[1], index)
			return area
		max_area = 0
		found_zero = False
		visited = set()
		index = 2
		area = {}
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				if grid[row][col] == 1:
					area[index] = dfs(row, col, index)
					index += 1
		max_area = max(area.values() or [0])
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				if grid[row][col] == 0:
					indexes = set()
					for direction in directions:
						new_row = row + direction[0]
						new_col = col + direction[1]
						if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and (grid[new_row][new_col] > 1):
							indexes.add(grid[new_row][new_col])
						max_area = max(max_area, sum((area[index] for index in indexes)) + 1)
		return max_area


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		if not grid:
			return
		(R, C) = (len(grid), len(grid[0]))
		directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		d = collections.defaultdict(int)

		def dfs(grid, row, col, idx):
			grid[row][col] = idx
			total = 1
			for di in directions:
				(newrow, newcol) = (row + di[0], col + di[1])
				if 0 <= newrow < R and 0 <= newcol < C and (grid[newrow][newcol] == 1):
					total += dfs(grid, newrow, newcol, idx)
			return total
		index = 2
		maxlength = 0
		for i in range(R):
			for j in range(C):
				if grid[i][j] == 1:
					total = 0
					total = dfs(grid, i, j, index)
					d[index] = total
					maxlength = max(maxlength, total)
					index += 1
		for i in range(R):
			for j in range(C):
				if grid[i][j] == 0:
					(keyset, length) = (set(), 0)
					for di in directions:
						(newrow, newcol) = (i + di[0], j + di[1])
						if 0 <= newrow < R and 0 <= newcol < C and (grid[newrow][newcol] > 1):
							keyset.add(grid[newrow][newcol])
					length = sum((d[key] for key in keyset)) + 1
					maxlength = max(length, maxlength)
		return max(1, maxlength)


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		N = len(grid)
		M = len(grid[0])

		def neighbors(r, c):
			result = []
			for (newR, newC) in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
				if 0 <= newR < N and 0 <= newC < M:
					result.append((newR, newC))
			return result

		def dfs(r, c, index):
			ans = 1
			grid[r][c] = index
			for (newR, newC) in neighbors(r, c):
				if grid[newR][newC] == 1:
					ans += dfs(newR, newC, index)
			return ans
		area = {}
		index = 2
		for r in range(N):
			for c in range(M):
				if grid[r][c] == 1:
					area[index] = dfs(r, c, index)
					index += 1
		ans = max(area.values() or [0])
		for r in range(N):
			for c in range(M):
				if grid[r][c] == 0:
					seen = {grid[newR][newC] for (newR, newC) in neighbors(r, c) if grid[newR][newC] > 1}
					ans = max(ans, 1 + sum((area[i] for i in seen)))
		return ans


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		N = len(grid)

		def neighbours(r, c):
			result = []
			for (nr, nc) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
				if 0 <= nr < N and 0 <= nc < N:
					result.append((nr, nc))
			return result

		def dfs(r, c, index):
			ans = 1
			grid[r][c] = index
			for (nr, nc) in neighbours(r, c):
				if grid[nr][nc] == 1:
					ans += dfs(nr, nc, index)
			return ans
		areas = {}
		index = 2
		for r in range(N):
			for c in range(N):
				if grid[r][c] == 1:
					areas[index] = dfs(r, c, index)
					index += 1
		ans = max(list(areas.values()) or [0])
		for r in range(N):
			for c in range(N):
				if grid[r][c] == 0:
					seen = {grid[nr][nc] for (nr, nc) in neighbours(r, c) if grid[nr][nc] > 1}
					ans = max(ans, 1 + sum((areas[i] for i in seen)))
		return ans


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		(M, N) = (len(grid), len(grid[0]))
		max_size = 0
		area_sizes = [0, 0]

		def mark(i, j) -> int:
			if not (0 <= i < M and 0 <= j < N):
				return 0
			if grid[i][j] != 1:
				return 0
			else:
				grid[i][j] = len(area_sizes)
			return 1 + mark(i - 1, j) + mark(i + 1, j) + mark(i, j - 1) + mark(i, j + 1)
		for i in range(M):
			for j in range(N):
				if grid[i][j] == 1:
					area_sizes.append(mark(i, j))
		max_size = max(max_size, *area_sizes)
		for i in range(M):
			for j in range(N):
				if grid[i][j] == 0:
					ids = set()
					if 0 <= i - 1:
						ids.add(grid[i - 1][j])
					if i + 1 < M:
						ids.add(grid[i + 1][j])
					if 0 <= j - 1:
						ids.add(grid[i][j - 1])
					if j + 1 < N:
						ids.add(grid[i][j + 1])
					max_size = max(max_size, sum((area_sizes[id] for id in ids)) + 1)
		return max_size


from typing import List
import math

class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		if grid == None or len(grid) == 0 or grid[0] == None or (len(grid[0]) == 0):
			return 0
		n = len(grid)
		m = len(grid[0])
		compSize = [0] * (n * m + 2)

		def dfs(x, y, c):
			nonlocal compSize
			nonlocal grid
			compSize[c] += 1
			grid[y][x] = c
			nextPoints = [[x - 1, y], [x, y - 1], [x + 1, y], [x, y + 1]]
			for point in nextPoints:
				nextX = point[0]
				nextY = point[1]
				if nextX < 0 or nextX == m or nextY < 0 or (nextY == n):
					continue
				if grid[nextY][nextX] == 1:
					dfs(nextX, nextY, c)
			return

		def calMaxLinkSize(x, y) -> int:
			nonlocal compSize
			nonlocal grid
			uniqueCompNums = []
			nextPoints = [[x - 1, y], [x, y - 1], [x + 1, y], [x, y + 1]]
			for point in nextPoints:
				nextX = point[0]
				nextY = point[1]
				if nextX < 0 or nextX == m or nextY < 0 or (nextY == n):
					continue
				compNum = grid[nextY][nextX]
				if compNum >= 2 and compNum not in uniqueCompNums:
					uniqueCompNums.append(compNum)
			return sum([compSize[c] for c in uniqueCompNums]) + 1
		compNum = 2
		maxCompSize = 0
		for y in range(n):
			for x in range(m):
				if grid[y][x] == 1:
					dfs(x, y, compNum)
					maxCompSize = max(maxCompSize, compSize[compNum])
					compNum += 1
		for y in range(n):
			for x in range(m):
				if grid[y][x] == 0:
					maxCompSize = max(maxCompSize, calMaxLinkSize(x, y))
		return maxCompSize

def __starting_point():
	pass
__starting_point()


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def dfs(i, j):
			dic[i, j] = curr
			count[curr] += 1
			for (dx, dy) in directions:
				(a, b) = (i + dx, j + dy)
				if 0 <= a < m and 0 <= b < n and (grid[a][b] == 1) and ((a, b) not in dic):
					dfs(a, b)

		def neighbours(i, j, adj):
			for (dx, dy) in directions:
				(a, b) = (i + dx, j + dy)
				if 0 <= a < m and 0 <= b < n and (grid[a][b] == 1) and (dic[a, b] not in adj):
					adj.add(dic[a, b])
			return adj
		(curr, dic, count, res) = (0, {}, collections.defaultdict(int), 0)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1 and (i, j) not in dic:
					curr += 1
					dfs(i, j)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					res = max(res, count[dic[i, j]])
				else:
					res = max(res, sum((count[r] for r in neighbours(i, j, set()))) + 1)
		return res


DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		N = len(grid)

		def move(x, y):
			ans = []
			for (mv_x, mv_y) in DIRECTIONS:
				x_ = x + mv_x
				y_ = y + mv_y
				if 0 <= x_ < N and 0 <= y_ < N:
					ans.append((x_, y_))
			return ans

		def dfs(x, y, idx):
			ans = 1
			grid[x][y] = idx
			for (i, j) in move(x, y):
				if grid[i][j] == 1:
					ans += dfs(i, j, idx)
			return ans
		idx = 2
		areas = {0: 0}
		for i in range(N):
			for j in range(N):
				if grid[i][j] == 1:
					areas[idx] = dfs(i, j, idx)
					idx += 1
		ans = max(areas.values())
		for i in range(N):
			for j in range(N):
				if grid[i][j] == 0:
					cands = set((grid[x][y] for (x, y) in move(i, j)))
					ans = max(ans, sum((areas[idx] for idx in cands)) + 1)
		return ans


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		parent = {}
		nums = collections.defaultdict(int)
		visited = set()
		res = 1
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and (i, j) not in parent:
					parent[i, j] = (i, j)
					stack = [(i, j)]
					while stack:
						(x, y) = stack.pop()
						nums[i, j] += 1
						directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
						for direction in directions:
							(dx, dy) = direction
							if self.is_valid(grid, (x + dx, y + dy), parent):
								parent[x + dx, y + dy] = (i, j)
								stack.append((x + dx, y + dy))
		for v in list(nums.values()):
			res = max(res, v)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					candidates = []
					directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
					for direction in directions:
						(dx, dy) = direction
						if i + dx < 0 or i + dx >= len(grid) or j + dy < 0 or (j + dy >= len(grid[0])):
							continue
						if grid[i + dx][j + dy] == 1:
							continue
						visited.add((i + dx, j + dy))
						res = max(res, nums[parent[i, j]] + 1)
						extra = 1
						temp_visited = set()
						for second_direction in directions:
							(ddx, ddy) = second_direction
							if i + dx + ddx < 0 or i + dx + ddx >= len(grid) or j + dy + ddy < 0 or (j + dy + ddy >= len(grid[0])):
								continue
							if grid[i + dx + ddx][j + dy + ddy] == 0:
								continue
							if parent[i + dx + ddx, j + dy + ddy] == parent[i, j]:
								continue
							if parent[i + dx + ddx, j + dy + ddy] in temp_visited:
								continue
							else:
								extra += nums[parent[i + dx + ddx, j + dy + ddy]]
								temp_visited.add(parent[i + dx + ddx, j + dy + ddy])
						res = max(res, nums[parent[i, j]] + extra)
		return res

	def is_valid(self, grid, pos, parent):
		(x, y) = pos
		if x < 0 or x >= len(grid) or y < 0 or (y >= len(grid[0])):
			return False
		if (x, y) in parent:
			return False
		if grid[x][y] == 0:
			return False
		return True


class Solution:

	def largestIsland(self, grid):
		(m, n, largest, areaMap) = (len(grid), len(grid[0]), 0, {})
		dirs = [[0, 1], [0, -1], [-1, 0], [1, 0]]

		def getIsland(cords, cord):
			if cord[0] < 0 or cord[0] >= m or cord[1] < 0 or (cord[1] >= n) or (not grid[cord[0]][cord[1]]):
				return
			if (cord[0], cord[1]) not in cords:
				cords.add(cord)
				for dir in dirs:
					getIsland(cords, (cord[0] + dir[0], cord[1] + dir[1]))
		for i in range(m):
			for j in range(n):
				if grid[i][j] and (i, j) not in areaMap:
					cubes = set()
					getIsland(cubes, (i, j))
					largest = max(largest, len(cubes))
					for c in cubes:
						areaMap[c] = cubes
		for i in range(m):
			for j in range(n):
				if not grid[i][j]:
					(area, areaSet) = (0, set())
					for dir in dirs:
						if (i + dir[0], j + dir[1]) in areaMap and (i + dir[0], j + dir[1]) not in areaSet:
							area += len(areaMap[i + dir[0], j + dir[1]])
							areaSet |= areaMap[i + dir[0], j + dir[1]]
					largest = max(largest, area + 1)
		return largest


class Solution:

	def largestIsland(self, matrix: List[List[int]]) -> int:

		def move(r, c):
			for (ri, ci) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
				(rn, cn) = (r + ri, c + ci)
				if 0 <= rn < len(matrix) and 0 <= cn < len(matrix[0]):
					yield (rn, cn)

		def dfs(r, c, idx):
			res = 1
			matrix[r][c] = idx
			for (rn, cn) in move(r, c):
				if matrix[rn][cn] == 1:
					res += dfs(rn, cn, idx)
			return res
		res = 0
		group = 2
		group_size = {0: 0}
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 1:
					count = dfs(i, j, group)
					group_size[group] = count
					res = max(res, count)
					group += 1
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 0:
					adjgrp = set((matrix[r][c] for (r, c) in move(i, j)))
					res = max(res, sum((group_size[grp] for grp in adjgrp)) + 1)
		return res


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		(M, N) = (len(grid), len(grid[0]))
		size = [0, 0]
		for i in range(M):
			for j in range(N):
				if grid[i][j] == 1:
					num = self.dfs(grid, i, j, len(size))
					size.append(num)
		res = 0
		for x0 in range(M):
			for y0 in range(N):
				if grid[x0][y0] == 0:
					tmpSum = 1
					tmpClr = set()
					for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
						x = x0 + dx
						y = y0 + dy
						if 0 <= x < M and 0 <= y < N:
							tmpClr.add(grid[x][y])
					for c in tmpClr:
						tmpSum += size[c]
					res = max(res, tmpSum)
		return res if res > 0 else M * N

	def dfs(self, grid, x0, y0, clr):
		grid[x0][y0] = clr
		res = 1
		for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			x = x0 + dx
			y = y0 + dy
			if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (grid[x][y] == 1):
				res += self.dfs(grid, x, y, clr)
		return res


class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:
		if not grid or len(grid) == 0:
			return 0
		nrows = len(grid)
		ncols = len(grid[0])
		islandid = 2
		maxsize = 0
		idsize = dict()

		def getIslandSize(grid, r, c, islandid):
			if not (0 <= r < nrows and 0 <= c < ncols) or grid[r][c] != 1:
				return 0
			grid[r][c] = islandid
			left = getIslandSize(grid, r, c - 1, islandid)
			right = getIslandSize(grid, r, c + 1, islandid)
			up = getIslandSize(grid, r - 1, c, islandid)
			down = getIslandSize(grid, r + 1, c, islandid)
			return left + right + up + down + 1
		for r in range(nrows):
			for c in range(ncols):
				if grid[r][c] == 1:
					size = getIslandSize(grid, r, c, islandid)
					maxsize = max(maxsize, size)
					idsize[islandid] = size
					islandid += 1
		for r in range(nrows):
			for c in range(ncols):
				if grid[r][c] == 0:
					islands = set()
					for direction in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
						newr = r + direction[0]
						newc = c + direction[1]
						if 0 <= newr < nrows and 0 <= newc < ncols and (grid[newr][newc] != 0):
							islands.add(grid[newr][newc])
					sum = 1
					for id in islands:
						sum += idsize[id]
					maxsize = max(maxsize, sum)
		return maxsize


from collections import defaultdict

class Solution:

	def largestIsland(self, grid: List[List[int]]) -> int:

		def dfs(m, n, c_id):
			nonlocal grid, c_dict
			stack = [(m, n)]
			size = 1
			while stack:
				(i, j) = stack.pop()
				children = [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]
				for (x, y) in children:
					if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (grid[x][y] == 1):
						grid[x][y] = c_id
						size += 1
						stack.append((x, y))
			c_dict[c_id] = size
		c_id = 1
		c_dict = defaultdict(int)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					c_id += 1
					grid[i][j] = c_id
					dfs(i, j, c_id)
		result = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] > 0:
					continue
				children = [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]
				n_c = set()
				for (x, y) in children:
					if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (grid[x][y] > 0):
						n_c.add(grid[x][y])
				result = max(result, sum([c_dict[c] for c in n_c]) + 1)
		return result if result > 0 else len(grid) * len(grid[0])