A potentialized disjoint set union on a group under a differential constraint system. Each vertex $v$ is assigned a potential value $p(v)$,

Example

>>> import AtCoder.Extra.Pdsu qualified as Pdsu
>>> import Data.Semigroup (Sum (..))
>>> dsu <- Pdsu.new @_ @(Sum Int) 4 negate

>>> Pdsu.merge dsu 1 0 (Sum 1)  -- p(1) - p(0) := Sum 1
True

>>> Pdsu.merge_ dsu 2 0 (Sum 2) -- p(2) - p(0) := Sum 2
>>> Pdsu.leader dsu 0
0

>>> Pdsu.pot dsu 0
Sum {getSum = 0}

>>> Pdsu.pot dsu 1
Sum {getSum = 1}

>>> Pdsu.pot dsu 2
Sum {getSum = 2}

>>> Pdsu.diff dsu 2 1
Just (Sum {getSum = 1})

>>> Pdsu.diff dsu 2 3
Nothing

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

Since: 1.1.0.0

$O(n)$ Creates a new DSU under a differential constraint system.

Since: 1.1.0.0

$O(\alpha(n))$ Returns the representative of the connected component that contains the vertex.

Since: 1.1.0.0

$O(\alpha(n))$ Returns $p(v)$, the potential value of vertex $v$ relative to the reprensetative of its group.

Since: 1.1.0.0

$O(\alpha(n))$ Returns the potential of $v_1$ relative to $v_2$: $p(v_1) \cdot p^{-1}(v_2)$ if the two vertices belong to the same group. Returns Nothing when the two vertices are not connected.

Since: 1.1.0.0

$O(\alpha(n))$ Returns the potential of $v_1$ relative to $v_2$: $p(v_1) \cdot p^{-1}(v_2)$ if the two vertices belong to the same group. Returns meaningless value if the two vertices are not connected.

Since: 1.1.0.0

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

Since: 1.1.0.0

$O(\alpha(n))$ Returns True if the two vertices belong to different groups or they belong to the same group under the condition $p(v_1) = dp \cdot p(v_2)$. It's just a convenient helper function.

Since: 1.1.0.0

$O(\alpha(n))$ Merges $v_1$ to $v_2$ with differential (relative) potential $\mathrm{dp}$: $p(v1) := \mathrm{dp} \cdot p(v2)$. Returns True if they're newly merged.

Since: 1.1.0.0

$O(\alpha(n))$ merge with the return value discarded.

Since: 1.1.0.0

$O(\alpha(n))$ Returns the number of vertices belonging to the same group.

Since: 1.1.0.0

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

Since: 1.1.0.0

$O(n)$ Clears the Pdsu to the initial state.

Since: 1.1.0.0