Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Dsu

Contents

Disjoint set union
Constructors
Merging
Leader
Component information

Description

A disjoint set union, also known as a Union-Find tree. It processes the following queries in amortized \(O(\alpha(n))\) time.

Edge addition (merge)
Deciding whether given two vertices are in the same connected component (same)

Each connected component internally has a representative vertex (leader). When two connected components are merged by edge addition (merge), one of the two representatives of these connected components becomes the representative (leader) of the new connected component.

Example

Expand

Create a Dsu with four vertices:

>>> import AtCoder.Dsu qualified as Dsu
>>> dsu <- Dsu.new 4   -- 0 1 2 3
>>> Dsu.nDsu dsu
4

Merge some vertices into the same group:

>>> Dsu.merge dsu 0 1  -- 0=1 2 3
0

>>> Dsu.merge_ dsu 1 2 -- 0=1=2 3

leader returns the internal representative vertex of the connected components:

>>> Dsu.leader dsu 2
0

Retrieve group information:

>>> Dsu.same dsu 0 2
True

>>> Dsu.size dsu 0
3

>>> Dsu.groups dsu
[[2,1,0],[3]]

Since: 1.0.0.0

Synopsis

data Dsu s
new :: PrimMonad m => Int -> m (Dsu (PrimState m))
merge :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> Int -> m Int
merge_ :: PrimMonad m => Dsu (PrimState m) -> Int -> Int -> m ()
leader :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> m Int
same :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> Int -> m Bool
size :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> m Int
groups :: PrimMonad m => Dsu (PrimState m) -> m (Vector (Vector Int))

Disjoint set union

data Dsu s Source #

A disjoint set union. Akso known as Union-Find tree.

Since: 1.0.0.0

Constructors

new :: PrimMonad m => Int -> m (Dsu (PrimState m)) Source #

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

Constraints

\(0 \le n\)

Complexity

\(O(n)\)

Since: 1.0.0.0

Merging

merge :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> 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.0.0.0

merge_ :: PrimMonad m => Dsu (PrimState m) -> 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.0.0.0

Leader

leader :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> 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.0.0.0

Component information

same :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> 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.0.0.0

size :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> 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.0.0.0

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

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.

Complexity

\(O(n)\)

Since: 1.0.0.0