AtCoder.Dsu

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

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

Disjoint set union

data Dsu s

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

Since: 1.0.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.0

Merging

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

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

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

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

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

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

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