Safe Haskell	None
Language	GHC2021

AtCoder.Extra.DsuMonoid

Contents

Disjoint set union
Constructors
Merging
Leader
Component information
Monoid values

Description

A disjoint set union with commutative semigroup (not necessary a monoid) values associated with each group.

Example

Expand

>>> import AtCoder.Extra.DsuMonoid qualified as Dm
>>> import Data.Semigroup (Sum (..))
>>> import Data.Vector.Unboxed qualified as VU
>>> dsu <- Dm.build $ VU.generate 4 Sum
>>> Dm.merge dsu 0 1
0

>>> Dm.read dsu 0
Sum {getSum = 1}

>>> Dm.read dsu 1
Sum {getSum = 1}

>>> Dm.mergeMaybe dsu 0 2
Just 0

>>> Dm.read dsu 0
Sum {getSum = 3}

Since: 1.5.3.0

Synopsis

data DsuMonoid s a
new :: (PrimMonad m, Monoid a, Unbox a) => Int -> m (DsuMonoid (PrimState m) a)
build :: (PrimMonad m, Semigroup a, Unbox a) => Vector a -> m (DsuMonoid (PrimState m) a)
merge :: (HasCallStack, PrimMonad m, Semigroup a, Unbox a) => DsuMonoid (PrimState m) a -> Int -> Int -> m Int
mergeMaybe :: (HasCallStack, PrimMonad m, Semigroup a, Unbox a) => DsuMonoid (PrimState m) a -> Int -> Int -> m (Maybe Int)
merge_ :: (PrimMonad m, Semigroup a, Unbox a) => DsuMonoid (PrimState m) a -> Int -> Int -> m ()
leader :: (HasCallStack, PrimMonad m) => DsuMonoid (PrimState m) a -> Int -> m Int
same :: (HasCallStack, PrimMonad m) => DsuMonoid (PrimState m) a -> Int -> Int -> m Bool
size :: (HasCallStack, PrimMonad m) => DsuMonoid (PrimState m) a -> Int -> m Int
groups :: PrimMonad m => DsuMonoid (PrimState m) a -> m (Vector (Vector Int))
read :: (PrimMonad m, Unbox a) => DsuMonoid (PrimState m) a -> Int -> m a
unsafeRead :: (PrimMonad m, Unbox a) => DsuMonoid (PrimState m) a -> Int -> m a
unsafeWrite :: (PrimMonad m, Unbox a) => DsuMonoid (PrimState m) a -> Int -> a -> m ()

Disjoint set union

data DsuMonoid s a Source #

A disjoint set union with commutative monoid values associated with each group.

Since: 1.5.3.0

Constructors

new :: (PrimMonad m, Monoid a, Unbox a) => Int -> m (DsuMonoid (PrimState m) a) Source #

Creates an undirected graph with \(n\) vertices and \(0\) edges.

Constraints

\(0 \le n\)

Complexity

\(O(n)\)

Since: 1.5.3.0

build :: (PrimMonad m, Semigroup a, Unbox a) => Vector a -> m (DsuMonoid (PrimState m) a) Source #

Creates an undirected graph with \(n\) vertices and \(0\) edges.

Constraints

\(0 \le n\)

Complexity

\(O(n)\)

Since: 1.5.3.0

Merging

merge :: (HasCallStack, PrimMonad m, Semigroup a, Unbox a) => DsuMonoid (PrimState m) a -> Int -> Int -> m Int Source #

Adds an edge \((a, b)\). If the vertices \(a\) and \(b\) are in the same connected component, it returns the representative (leader) of this connected component. Otherwise, it returns the representative of the new connected component.

Constraints

\(0 \leq a < n\)
\(0 \leq b < n\)

Complexity

\(O(\alpha(n))\) amortized

Since: 1.5.3.0

mergeMaybe :: (HasCallStack, PrimMonad m, Semigroup a, Unbox a) => DsuMonoid (PrimState m) a -> Int -> Int -> m (Maybe Int) Source #

Adds an edge \((a, b)\). It returns the representative of the new connected component, or Nothing if the two vertices are in the same connected component.

Constraints

\(0 \leq a < n\)
\(0 \leq b < n\)

Complexity

\(O(\alpha(n))\) amortized

Since: 1.5.3.0

merge_ :: (PrimMonad m, Semigroup a, Unbox a) => DsuMonoid (PrimState m) a -> Int -> Int -> m () Source #

merge with the return value discarded.

Constraints

\(0 \leq a < n\)
\(0 \leq b < n\)

Complexity

\(O(\alpha(n))\) amortized

Since: 1.5.3.0

Leader

leader :: (HasCallStack, PrimMonad m) => DsuMonoid (PrimState m) a -> Int -> m Int Source #

Returns the representative of the connected component that contains the vertex \(a\).

Constraints

\(0 \leq a \lt n\)

Complexity

\(O(\alpha(n))\) amortized

Since: 1.5.3.0

Component information

same :: (HasCallStack, PrimMonad m) => DsuMonoid (PrimState m) a -> Int -> Int -> m Bool Source #

Returns whether the vertices \(a\) and \(b\) are in the same connected component.

Constraints

\(0 \leq a < n\)
\(0 \leq b < n\)

Complexity

\(O(\alpha(n))\) amortized

Since: 1.5.3.0

size :: (HasCallStack, PrimMonad m) => DsuMonoid (PrimState m) a -> Int -> m Int Source #

Returns the size of the connected component that contains the vertex \(a\).

Constraints

\(0 \leq a < n\)

Complexity

\(O(\alpha(n))\)

Since: 1.5.3.0

groups :: PrimMonad m => DsuMonoid (PrimState m) a -> m (Vector (Vector Int)) Source #

O(n)) Divides the graph into connected components and returns the vector of them.

More precisely, it returns a vector of the "vector of the vertices in a connected component". Both of the orders of the connected components and the vertices are undefined.

Since: 1.5.3.0

Monoid values

read :: (PrimMonad m, Unbox a) => DsuMonoid (PrimState m) a -> Int -> m a Source #

\(O(1)\) Reads the group value of the \(k\)-th node.

Since: 1.5.3.0

unsafeRead :: (PrimMonad m, Unbox a) => DsuMonoid (PrimState m) a -> Int -> m a Source #

\(O(1)\) Reads the group value of the \(k\)-th node.

Since: 1.5.3.0

unsafeWrite :: (PrimMonad m, Unbox a) => DsuMonoid (PrimState m) a -> Int -> a -> m () Source #

\(O(1)\) Writes to the group value of the \(k\)-th node.

Since: 1.5.3.0