• Effekt Logo Effekt Library
    • union_find
      • UnionFind
      • isRoot
      • parent
      • rank
      • setParent
      • setRank
      • unionFind
      • unionFind
      • makeSet
      • find
      • unionRoots
      • union
    • union_find
      • Jump to source: libraries/common/union_find.effekt
      Example usage: examples/stdlib/union_find
      • UnionFind (rawElements: ResizableArray[Int])
        • Classic mutable union-find data structure on integer indices,
with union-by-rank and path compression.
      • isRoot (u: UnionFind, s: Int): Bool / {Exception[MissingValue]}
      • parent (u: UnionFind, s: Int): Int / {Exception[MissingValue]}
      • rank (u: UnionFind, s: Int): Int / {Exception[MissingValue]}
      • setParent (u: UnionFind, child: Int, parent: Int)
      • setRank (u: UnionFind, root: Int, rank: Int)
      • unionFind : UnionFind / {}
      • unionFind (capacity: Int): UnionFind / {}
      • makeSet (u: UnionFind): Int / {} 
        • Make a new set in the union-find datastructure and return its index

O(1) amortized, worst-case O(n) if the capacity does not suffice
      • find (u: UnionFind, s: Int): Int / {Exception[MissingValue]} 
        • Find the representative of the given element.

O(inverse-ackermann(n)) amortized
      • unionRoots (u: UnionFind, x: Int, y: Int): Int / {Exception[MissingValue]} 
        • Make it such that the sets *represented by* x and y are merged

O(1)
      • union (u: UnionFind, a: Int, b: Int): Int / {Exception[MissingValue]} 
        • Make it so a and b are in the same set

O(inverse-ackermann(n)) amortized