data_structures.disjoint_set.alternate_disjoint_set

Implements a disjoint set using Lists and some added heuristics for efficiency Union by Rank Heuristic and Path Compression

Classes

DisjointSet

Module Contents

class data_structures.disjoint_set.alternate_disjoint_set.DisjointSet(set_counts: list)

get_parent(disj_set: int) → int

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

merge(src: int, dst: int) → bool

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

max_set

num_sets

parents

ranks

set_counts