Safe Haskell	None
Language	Haskell2010

DSU

Description

Disjoint set union

Data structure to maintain disjoint sets of Ints, supporting find and union. Uses union by size and path halving.

Sources:

https://en.wikipedia.org/wiki/Disjoint-set_data_structure
https://cp-algorithms.com/data_structures/disjoint_set_union.html
https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/UnionFind.h
Robert E. Tarjan and Jan van Leeuwen, "Worst-Case Analysis of Set Union Algorithms", 1984 https://dl.acm.org/doi/10.1145/62.2160

Use unboxed arrays (IOUArray/STUArray) for best performance! n = r - l + 1 in all instances below. α is the inverse Ackermann function.

Synopsis

newD :: MArray a Int m => (Int, Int) -> m (a Int Int)
sameSetD :: MArray a Int m => a Int Int -> Int -> Int -> m Bool
unionD :: MArray a Int m => a Int Int -> Int -> Int -> m Bool

Documentation

newD :: MArray a Int m => (Int, Int) -> m (a Int Int) Source #

Creates a new DSU structure with elements in the range (l, r), each in its own set. O(n).

sameSetD :: MArray a Int m => a Int Int -> Int -> Int -> m Bool Source #

Returns whether the two elements are in the same set. Amortized O(α(n)).

unionD :: MArray a Int m => a Int Int -> Int -> Int -> m Bool Source #

Unites the sets containing the two elements. If they are already in the same set, returns False, otherwise performs the union and returns True. Amortized O(α(n)).