USE PYTHON PROGRAMMING. The expected outputs seen in the screenshot must be achieved. (Not working = Thumbs Down) You must use the code template below. You cannot modify the class or its methods. You are only allowed to add lines of code to the main part of the program. Thank you. 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--
USE PYTHON PROGRAMMING.
The expected outputs seen in the screenshot must be achieved. (Not working = Thumbs Down)
You must use the code template below. You cannot modify the class or its methods. You are only allowed to add lines of code to the main part of the program. Thank you.
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--
Step by step
Solved in 2 steps with 1 images