You are given an n x n binary grid. A grid is said to be binary if every value in grid is either 1 or 0.
You can change at most one cell in grid from 0 to 1.
You need to find the largest group of connected  1's.
Two cells are said to be connected if both are adjacent to each other and both have same value.
Example 1
Input:
2
1 1
0 1
Output:
4
Explanation:
By changing cell (2,1) ,we can obtain a connected group of 4 1's
1 1
1 1
 
Example 2
Input:
3
1 0 1
1 0 1
1 0 1
Output:
7
Explanation:
By changing cell (3,2) ,we can obtain a connected group of 7 1's
1 0 1
1 0 1
1 1 1
Your Task:
You don't need to read or print anything. Your task is to complete the function MaxConnection() which takes a matrix grid[][] denoting the grid and return the maximum group of connected group of 1s.
 
Constraints:
1 <= n<= 500
0 <= grid[i][j] <= 1

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: from typing import List





class Solution:

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

        # code here

        



Solutions:
from typing import List
from collections import defaultdict

class DSU:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.rank = [0] * n

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

	def union(self, u, v):
		(u_p, v_p) = (self.find(u), self.find(v))
		if u_p == v_p:
			return
		if self.rank[u_p] > self.rank[v_p]:
			self.par[v_p] = u_p
		elif self.rank[u_p] < self.rank[v_p]:
			self.par[u_p] = v_p
		else:
			self.par[u_p] = v_p
			self.rank[u_p] += 1

class Solution:

	def MaxConnection(self, grid: List[List[int]]) -> int:
		n = len(grid)
		dsu = DSU(n * n)
		vis = set()
		dire = [(-1, 0), (0, 1), (1, 0), (0, -1)]

		def first_dfs(par_r, par_c, r, c):
			if r < 0 or c < 0 or r >= n or (c >= n) or ((r, c) in vis) or (grid[r][c] != 1):
				return
			vis.add((r, c))
			dsu.union(par_r * n + par_c, r * n + c)
			for i in dire:
				(x, y) = (r + i[0], c + i[1])
				first_dfs(par_r, par_c, x, y)
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1 and (i, j) not in vis:
					first_dfs(i, j, i, j)
		d = defaultdict(int)
		for i in dsu.par:
			d[dsu.find(i)] += 1
		maxi = 0
		for i in range(n):
			for j in range(n):
				if (i, j) not in vis and grid[i][j] == 0:
					new = set()
					ans = 1
					for k in dire:
						(x, y) = (i + k[0], j + k[1])
						if x >= 0 and y >= 0 and (x < n) and (y < n) and (grid[x][y] == 1):
							val = dsu.find(x * n + y)
							if val in new:
								continue
							new.add(val)
							ans += d[val]
					maxi = max(ans, maxi)
		if maxi:
			return maxi
		return n * n


from typing import List

class UnionFind:

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

	def union(self, u, v):
		parent_u = self.find(u)
		parent_v = self.find(v)
		if parent_u == parent_v:
			return True
		if self.size[parent_u] < self.size[parent_v]:
			self.parent[parent_u] = parent_v
			self.size[parent_v] += self.size[parent_u]
		else:
			self.parent[parent_v] = parent_u
			self.size[parent_u] += self.size[parent_v]
		return False

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

class Solution:

	def MaxConnection(self, grid: List[List[int]]) -> int:
		n = len(grid)
		ds = UnionFind(n * n)
		for row in range(n):
			for col in range(n):
				if grid[row][col] == 0:
					continue
				directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
				for (dx, dy) in directions:
					newRow = row + dx
					newCol = col + dy
					if newRow >= 0 and newRow < n and (newCol >= 0) and (newCol < n) and (grid[newRow][newCol] == 1):
						nodeCellNo = row * n + col
						adjacentNodeCellNo = newRow * n + newCol
						ds.union(nodeCellNo, adjacentNodeCellNo)
		maxSize = 0
		for row in range(n):
			for col in range(n):
				if grid[row][col] == 1:
					continue
				directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
				Components = set()
				for (dx, dy) in directions:
					newRow = row + dx
					newCol = col + dy
					if newRow >= 0 and newRow < n and (newCol >= 0) and (newCol < n):
						if grid[newRow][newCol] == 1:
							Components.add(ds.find(newRow * n + newCol))
				sizeTotal = 0
				for component in Components:
					sizeTotal += ds.size[component]
				maxSize = max(maxSize, sizeTotal + 1)
		maxSize = max(maxSize, ds.size[ds.find(0)])
		return maxSize


from typing import List

class DisjointSet:

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

	def findUParent(self, node):
		if node == self.parent[node]:
			return node
		self.parent[node] = self.findUParent(self.parent[node])
		return self.parent[node]

	def unionByRank(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.rank[up_u] < self.rank[up_v]:
			self.parent[up_u] = up_v
		elif self.rank[up_v] < self.rank[up_u]:
			self.parent[up_v] = up_u
		else:
			self.parent[up_v] = up_u
			self.rank[up_u] += 1
		return

	def unionBySize(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.size[up_u] < self.size[up_v]:
			self.parent[up_u] = up_v
			self.size[up_v] += self.size[up_u]
		else:
			self.parent[up_v] = up_u
			self.size[up_u] += self.size[up_v]
		return

class Solution:

	def MaxConnection(self, grid: List[List[int]]) -> int:
		n = len(grid)
		ds = DisjointSet(n * n)
		dr = [-1, 1, 0, 0]
		dc = [0, 0, -1, 1]
		vis = set()
		for i in range(n):
			for j in range(n):
				node = i * n + j
				if grid[i][j] == 1:
					for k in range(len(dr)):
						nr = i + dr[k]
						nc = j + dc[k]
						if 0 <= nr < n and 0 <= nc < n and (grid[nr][nc] == 1):
							ds.unionBySize(node, nr * n + nc)
		maxi = 0
		for i in range(n):
			for j in range(n):
				s = set()
				if grid[i][j] == 0:
					for k in range(len(dr)):
						nr = i + dr[k]
						nc = j + dc[k]
						if 0 <= nr < n and 0 <= nc < n and (grid[nr][nc] == 1):
							s.add(ds.findUParent(nr * n + nc))
					maxi = max(maxi, 1 + sum([ds.size[x] for x in s]))
		for cell in range(n * n):
			maxi = max(maxi, ds.size[ds.findUParent(cell)])
		return maxi