implements a disjoint set using lists and some added heuristics for efficiency union by rank heuristic and path compression initialize with a list of the number of items in each set and with rank 1 for each set merge two sets together using union by rank heuristic return true if successful merge two disjoint sets a disjointset1 1 1 a merge1 2 true a merge0 2 true a merge0 1 false find the parent of a given set a disjointset1 1 1 a merge1 2 true a getparent0 0 a getparent1 2 initialize with a list of the number of items in each set and with rank 1 for each set merge two sets together using union by rank heuristic return true if successful merge two disjoint sets a disjointset 1 1 1 a merge 1 2 true a merge 0 2 true a merge 0 1 false find the parent of a given set a disjointset 1 1 1 a merge 1 2 true a get_parent 0 0 a get_parent 1 2
class DisjointSet:
    def __init__(self, set_counts: list) -> None:
        
        self.set_counts = set_counts
        self.max_set = max(set_counts)
        num_sets = len(set_counts)
        self.ranks = [1] * num_sets
        self.parents = list(range(num_sets))

    def merge(self, src: int, dst: int) -> bool:
        
        src_parent = self.get_parent(src)
        dst_parent = self.get_parent(dst)

        if src_parent == dst_parent:
            return False

        if self.ranks[dst_parent] >= self.ranks[src_parent]:
            self.set_counts[dst_parent] += self.set_counts[src_parent]
            self.set_counts[src_parent] = 0
            self.parents[src_parent] = dst_parent
            if self.ranks[dst_parent] == self.ranks[src_parent]:
                self.ranks[dst_parent] += 1
            joined_set_size = self.set_counts[dst_parent]
        else:
            self.set_counts[src_parent] += self.set_counts[dst_parent]
            self.set_counts[dst_parent] = 0
            self.parents[dst_parent] = src_parent
            joined_set_size = self.set_counts[src_parent]

        self.max_set = max(self.max_set, joined_set_size)
        return True

    def get_parent(self, disj_set: int) -> int:
        
        if self.parents[disj_set] == disj_set:
            return disj_set
        self.parents[disj_set] = self.get_parent(self.parents[disj_set])
        return self.parents[disj_set]