Answer Happy

PYTHON PROGRAMMING
Implementation of
WeightedQuickUnion
please show that the output is the same as the provided below.
Thank you!
CODE FORMAT
import ast
class WeightedQuickUnion:
def __init__(self, size: int) -> None:
"""
Initializes the union-find ds
size: number of elements to initialize
"""
self.size = size
self.parent = [-1]*self.size # create a list where all elements are
roots
self.group_size = [1]*self.size # create separate list to indicate
the size for each element
# (useful for knowing the size in root's perspective)

def __str__(self) -> str:
return f"parent: {self.parent}\nsize: {self.group_size}\n"
def get_root(self, p: int) -> int:
"""Find the root of p"""
idx = p
while self.parent[idx] >= 0: # root should have a negative
value
idx = self.parent[idx]
return idx
def is_connected(self, p1: int, p2:int) -> bool:
return self.get_root(p1) == self.get_root(p2)
def connect(self, p1: int, p2: int) -> None:
"""Connects p1 and p2"""
r1 = self.get_root(p1)
r2 = self.get_root(p2)
r1_size = self.group_size[r1]
r2_size = self.group_size[r2]
if r1_size > r2_size:
self.parent[r2] = r1
self.group_size[r1] += r2_size # increase r1 group size by r2
size
else:
self.parent[r1] = r2
self.group_size[r2] += r1_size # increase r2 group size by r1
size
if __name__ == "__main__":
board = input()
board = ast.literal_eval(board)
num_rows, num_cols = len(board), len(board[0])
uf = WeightedQuickUnion(size = num_rows*num_cols)
#### INSERT CODE HERE ####
• You are employed by Microsoft. Unexpectedly, Minesweeper is gaining popularity again and users are requesting for additional features. Your boss wanted you to help add features in the codebase. You are tasked to create a helper function that will display the maximum number of bombs that are clustered together. This is so players can have an idea how scattered the bombs are. Upon looking into the codebase, you saw that your coworker recently developed an implementation of Weighted Quick Union with the intention of using it for another feature. When your boss found out, he/she told you to use it so you can brush up on your data structures knowledge. . Given the Minesweeper board below, you should output "4" since the maximum number of bombs (marked as "x") that are beside each other is 4. Two bombs are considered beside each other if they are horizontally or vertically touching (diagonals are not considered). X x X X X X Input Format • You will be given a list of lists in the following form: 11 11 [["x", 1," "],["x", ",""],[" "]]

Constraints You are required to use the provided WeightedQuickUnion class • assume all elements of the list are valid (i.e., only "X" and "" are in the list of lists) • assume all list of lists have valid and consistent sizes (i.e, no list will have a different size from other lists) Output Format • You are supposed to output the maximum number of bombs that form a group The output should only be one number 4 Sample Input 0 1 [["x","x ",""],["x", ,"x"]] Sample Output 0

Sample Input 1 [I" "," "]] Sample Output 1

import ast -class WeightedQuickUnion: def __init__(self, size: int) -> None: I! Initializes the union-find ds size: number of elements to initialize self.size size self.parent = [-1]*self.size # create a list where all elements are roots self.group_size = [1]*self.size # create separate list to indicate the size for each element # (useful for knowing the size in root's perspective) def __str__(self) -> str: return f"parent: {self.parent}\nsize: {self.group_size}\n" def get_root (self, p: int) -> int: Find the root of p idx = p while self.parent[idx] idx = self.parent[idx] return idx >= 0 : # root should have a negative value def is_connected(self, pl: int, p2:int) -> bool: return self.get_root(pl) self.get_root(p2)

def connect (self, pl: int, p2: int) -> None: "Connects pl and p2" rl = self.get_root(pl) r2 = self.get_root(p2) ri_size = self.group_size[rl] r2_size = self.group_size[r2] if ri_size > r2_size: self.parent [r2] = ri self.group_size[ri] += r2_size # increase rl group size by r2 size else: self.parent[ri] = r2 self.group_size[r2] += ri_size # increase r2 group size by rl size if -_name__ == "__main__": board = input() board - ast. literal_eval(board) num_rows, num_cols = len(board), len(board[0]) uf = WeightedQuickUnion(size = num_rows* num_cols) #### INSERT CODE HERE ####