Safe Haskell	None
Language	GHC2021

AtCoder.Dsu

Contents

Disjoint set union
Constructor
Merge
Leader
Component information

Description

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

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

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

Example

Expand

Create DSU:

>>> 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: b:

>>> 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

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 #

Disjoint set union. Akso known as Union-Find tree.

Since: 1.0.0

Constructor

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

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

Constraints

\(0 \le n\)

Complexity

\(O(n)\)

Since: 1.0.0

Merge

merge :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> Int -> m Int #

Adds an edge (a, b). the vertices a and b were in the same connected component, it returns the representative 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

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

merge with return value discarded.

Constraints

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

Complexity

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

Since: 1.0.0

Leader

leader :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> m Int #

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

same :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> Int -> m Bool #

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

Component information

size :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> m Int #

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

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

Divides the graph into connected components and returns the list 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