Skip to Content
ReferenceLibrary

dsu

A point in the history of a structure that can step back in time, returned by mark() and taken by undo_to.

Generated from spec/std/dsu.cp by cpl doc --format json.

Mark

pub struct Mark(at

A point in the history of a structure that can step back in time, returned by mark() and taken by undo_to. Its own type, so it can't be mixed up with a count or an index.

Source

Dsu

pub struct Dsu<V>

Union-find with path halving and union by size. find, unite, same and size are O(alpha(n)) amortized; memory is one [V] array (4 B/vertex).

It can also step back in time: let snap = d.mark() remembers the present and d.undo_to(snap) returns to it. From the first mark on, paths are no longer shortened (a shortened path cannot be restored), so every operation is O(log n) and each unite costs one entry of memory until it is undone.

Source

Dsu.joined

joined: List<Int>

Pairs [child_ord, old_neg_size] pushed flat since the first mark.

Source

Dsu.new

fn new(rollback: Bool = false) -> Dsu<V>

A union-find over V with every position in its own set. Pass rollback: true to switch path shortening off from the start, as the first mark() would.

  • cost: O(n) for n = V.count; one [V] array
  • traps: never

Examples:

  • let d = Dsu<0..3>(); d.components == 3

Source

Dsu.find_ord

fn find_ord(self, start: Int) -> Int

Source

Dsu.find

fn find(self, v: V) -> V

The representative of v's set: the root that union by size kept. Two positions are in one set exactly when they have the same representative.

Halves the path it walks through @cache, so a read-only Dsu answers it too; from the first mark on, paths are left alone.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark
  • ties: None; the representative is fixed by the merges (larger set's root, a's root on equal sizes)
  • traps: never

Examples:

  • var d = Dsu<0..4>(); d.unite(2, 3); d.find(3) == 2 and d.find(0) == 0

Source

Dsu.mark

fn mark(mut self) -> Mark

The present, to return to with undo_to. The first call switches path shortening off for good.

  • cost: O(1)
  • traps: never

Examples:

  • var d = Dsu<0..3>(); let m = d.mark(); d.unite(0, 1); d.undo_to(m); d.components == 3

Source

Dsu.undo_to

fn undo_to(mut self, snap: Mark)

Undoes every unite made since snap = mark(), newest first, so the sets, sizes and representatives are exactly what they were at the mark. Marks nest: undoing to an older mark passes over newer ones.

  • cost: O(1) per undone unite
  • traps: when snap lies after the present (its changes were already undone)

Examples:

  • var d = Dsu<0..3>(); d.unite(0, 1); let m = d.mark(); d.unite(1, 2); d.undo_to(m); d.same(0, 1) and not d.same(0, 2)

Source

Dsu.unite

fn unite(mut self, a: V, b: V) -> Bool

Merges the sets of a and b; false if they were already one set (nothing changes then).

The root of the larger set is kept; on equal sizes a's root is kept.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark, plus one log entry
  • traps: never

Examples:

  • var d = Dsu<0..3>(); d.unite(0, 1) and not d.unite(1, 0)

Source

Dsu.merge

fn merge(mut self, a: V, b: V) -> ?(kept: V, merged: V)

As unite, but says which root stayed and which went under it, so data kept per set can follow: if let (kept, merged) = d.merge(a, b): sum[kept] += sum[merged]. None if a and b were already one set.

  • cost: as unite
  • traps: never

Examples:

  • var d = Dsu<0..3>(); d.merge(1, 0) == Some((kept: 1, merged: 0))
  • var d = Dsu<0..3>(); d.unite(0, 1); d.merge(2, 1) == Some((kept: 0, merged: 2))
  • var d = Dsu<0..3>(); d.unite(0, 1); d.merge(1, 0) == None

Source

Dsu.same

fn same(self, a: V, b: V) -> Bool

Whether a and b are in the same set.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark
  • traps: never

Examples:

  • var d = Dsu<0..3>(); d.unite(0, 2); d.same(2, 0) and not d.same(0, 1)

Source

Dsu.size

fn size(self, v: V) -> Int

The number of positions in v's set, v included.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark
  • traps: never

Examples:

  • var d = Dsu<0..3>(); d.unite(0, 2); d.size(2) == 2 and d.size(1) == 1

Source

Dsu.components

fn components(self) -> Int

The number of sets: V.count minus the successful unites still in effect.

  • cost: O(1)
  • traps: never

Examples:

  • var d = Dsu<0..4>(); d.unite(0, 1); d.unite(1, 0); d.components == 3

Source

Dsu.roots

fn roots(self) -> yields V

The representative of each set, once each, lazily.

  • cost: O(n) for the whole walk, no allocation
  • empty: yields nothing when V is empty
  • order: increasing positions of V
  • traps: never

Examples:

  • var d = Dsu<0..4>(); d.unite(3, 1); d.roots().collect() == [0, 2, 3]

Source

Dsu.groups

fn groups(self) -> List<List<V>>

Every set as a list of its positions, each position in exactly one list.

  • cost: O(n alpha(n)); allocates the lists
  • empty: [] when V is empty
  • order: lists by their least position, positions increasing within each
  • traps: never

Examples:

  • var d = Dsu<0..4>(); d.unite(3, 1); d.groups() == [[0], [1, 3], [2]]

Source

DsuOf

pub struct DsuOf<V, T>

Union-find where every set carries a value of type T. When two sets merge, the merged set gets join(value of a's set, value of b's set) for unite(a, b), whichever root is kept, so a directional join like (_, b) => b means "b's value wins". Costs are those of Dsu, plus one join per merge; memory is three [V] arrays.

mark and undo_to step back in time like Dsu's, and restore the values too: every merge and every set since the mark is undone, O(1) each.

Source

DsuOf.log

log: List<(V, V, T)>

Since the first mark, one entry per change: the root that went under another (the root itself for a set), the root whose value changed, and that value before.

Source

DsuOf.new

fn new(init: (V) -> T, join: (T, T) -> T) -> DsuOf<V, T>

A union-find over V with every position alone, the set of v holding init(v), and join combining the values of two sets when they merge.

  • cost: O(n) calls of init; three [V] arrays
  • traps: never

Examples:

  • let d = DsuOf<0..3, Int>(init: v => v + 1, join: (x, y) => x + y); d.get(2) == 3

Source

DsuOf.find

fn find(self, v: V) -> V

The representative of v's set, as for Dsu.find. Halves paths through @cache until the first mark.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark
  • ties: None; the representative is fixed by the merges (larger set's root, a's root on equal sizes)
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.unite(1, 2); d.find(2) == 1

Source

DsuOf.get

fn get(self, v: V) -> T

The value of v's set.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v + 1, join: (x, y) => x + y); d.unite(0, 2); d.get(2) == 4 and d.get(1) == 2

Source

DsuOf.set

fn set(mut self, v: V, x: T)

Replaces the value of v's whole set with x.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark, plus one log entry
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.unite(0, 1); d.set(1, 7); d.get(0) == 7

Source

DsuOf.unite

fn unite(mut self, a: V, b: V) -> Bool

Merges the sets of a and b, giving the merged set join(value of a's set, value of b's set) in that argument order whichever root is kept; false if they were already one set (the value is left alone then and join is not called).

The root of the larger set is kept; on equal sizes a's root is kept.

  • cost: as Dsu.unite, plus one call of join
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (_, y) => y); d.unite(2, 0); d.get(2) == 0
  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.unite(0, 1); not d.unite(1, 0) and d.get(0) == 1

Source

DsuOf.merge

fn merge(mut self, a: V, b: V) -> ?(kept: V, merged: V)

As unite, but says which root stayed and which went under it. None if a and b were already one set.

  • cost: as unite
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.merge(2, 1) == Some((kept: 2, merged: 1))

Source

DsuOf.same

fn same(self, a: V, b: V) -> Bool

Whether a and b are in the same set.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.unite(0, 2); d.same(0, 2) and not d.same(1, 2)

Source

DsuOf.size

fn size(mut self, v: V) -> Int

The number of positions in v's set, v included.

  • cost: O(alpha(n)) amortized; O(log n) after the first mark
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.unite(0, 2); d.size(0) == 2

Source

DsuOf.components

fn components(self) -> Int

The number of sets.

  • cost: O(1)
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.unite(0, 2); d.components == 2

Source

DsuOf.roots

fn roots(self) -> yields V

The representative of each set, once each, lazily.

  • cost: O(n) for the whole walk, no allocation
  • empty: yields nothing when V is empty
  • order: increasing positions of V
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.unite(2, 0); d.roots().collect() == [1, 2]

Source

DsuOf.values

fn values(self) -> yields T

The value of each set, once each, lazily: one per root, in the order of roots. O(1) to make.

  • cost: O(n) for the whole walk, no allocation
  • empty: yields nothing when V is empty
  • order: by representative, increasing positions of V
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v + 1, join: (x, y) => x + y); d.unite(2, 0); d.values.collect() == [2, 4]

Source

DsuOf.mark

fn mark(mut self) -> Mark

The present, to return to with undo_to. The first call switches path shortening off for good.

  • cost: O(1)
  • traps: never

Examples:

  • var d = DsuOf<0..2, Int>(init: v => v, join: (x, y) => x + y); let m = d.mark(); d.unite(0, 1); d.undo_to(m); d.get(0) == 0

Source

DsuOf.undo_to

fn undo_to(mut self, snap: Mark)

Undoes every merge and every set made since snap = mark(), newest first, restoring the sets and their values exactly.

  • cost: O(1) per undone change
  • traps: when snap lies after the present (its changes were already undone)

Examples:

  • var d = DsuOf<0..2, Int>(init: v => v, join: (x, y) => x + y); let m = d.mark(); d.unite(0, 1); d.set(0, 9); d.undo_to(m); d.get(0) == 0 and d.get(1) == 1

Source

DsuOf.groups

fn groups(mut self) -> List<List<V>>

Every set as a list of its positions, as Dsu.groups; values are read with get.

  • cost: O(n alpha(n)); allocates the lists
  • empty: [] when V is empty
  • order: lists by their least position, positions increasing within each
  • traps: never

Examples:

  • var d = DsuOf<0..3, Int>(init: v => v, join: (x, y) => x + y); d.unite(2, 0); d.groups() == [[0, 2], [1]]

Source

ParityDsu

pub struct ParityDsu<V>

Union-find that knows, for two positions of one set, whether they are on the same side or on opposite sides: two-colouring, parity constraints, x[a] xor x[b] == d. unite and diff are O(log n) (union by size; paths are never shortened, so mark and undo_to work at any time, O(1) per undone unite). Memory is three [V] arrays.

Source

ParityDsu.flip

flip: [V]Bool

Is the position on the other side from up of it?

Source

ParityDsu.log

log: List<(V, Bool)>

One entry per unite that changed something: the root it hung under another root, or (with false) the root of a set where it found a contradiction.

Source

ParityDsu.new

fn new() -> ParityDsu<V>

A parity union-find over V with every position alone and nothing known.

  • cost: O(n); three [V] arrays
  • traps: never

Examples:

  • let d = ParityDsu<0..3>(); d.consistent and d.diff(0, 1) == None

Source

ParityDsu.find

fn find(self, v: V) -> (root: V, flip: Bool)

The representative of v's set and whether v is on the other side from it.

  • cost: O(log n)
  • ties: None; the representative is fixed by the merges (larger set's root, a's root on equal sizes)
  • traps: never

Examples:

  • var d = ParityDsu<0..3>(); d.unite(0, 1); d.find(1) == (root: 0, flip: true)
  • let d = ParityDsu<0..3>(); d.find(2) == (root: 2, flip: false)

Source

ParityDsu.unite

fn unite(mut self, a: V, b: V, differ: Bool = true) -> Bool

Records that a and b are on opposite sides (differ: false: the same side). An edge of a graph is unite(u, v).

Returns false when that contradicts what is already known: nothing is merged, the contradiction is counted, and consistent stays false until it is undone. A constraint that is already implied returns true and changes nothing. Merging keeps the larger set's root, a's root on equal sizes.

  • cost: O(log n), plus one log entry when it merges or contradicts
  • traps: never

Examples:

  • var d = ParityDsu<0..3>(); d.unite(0, 1); d.unite(1, 2); not d.unite(0, 2) and not d.consistent
  • var d = ParityDsu<0..3>(); d.unite(0, 1); d.unite(1, 2); d.unite(0, 2, differ: false) and d.consistent

Source

ParityDsu.diff

fn diff(self, a: V, b: V) -> ?Bool

Whether a and b are on opposite sides; None when nothing relates them yet.

  • cost: O(log n)
  • traps: never

Examples:

  • var d = ParityDsu<0..3>(); d.unite(0, 1); d.unite(1, 2); d.diff(0, 2) == Some(false) and d.diff(1, 0) == Some(true)
  • ParityDsu<0..3>().diff(0, 2) == None

Source

ParityDsu.same

fn same(self, a: V, b: V) -> Bool

Whether a and b are in the same set, so that their relative side is known.

  • cost: O(log n)
  • traps: never

Examples:

  • var d = ParityDsu<0..3>(); d.unite(0, 1); d.same(1, 0) and not d.same(0, 2)

Source

ParityDsu.size

fn size(self, v: V) -> Int

The number of positions in v's set, v included.

  • cost: O(log n)
  • traps: never

Examples:

  • var d = ParityDsu<0..3>(); d.unite(0, 1); d.unite(1, 2); d.size(2) == 3

Source

ParityDsu.consistent

fn consistent(self) -> Bool

Whether no contradiction is in effect: every unite since the last undone one agreed with those before it. For a graph: is it two-colourable?

  • cost: O(1)
  • traps: never

Examples:

  • var d = ParityDsu<0..3>(); d.unite(0, 1); d.unite(1, 2); d.unite(2, 0); not d.consistent

Source

ParityDsu.mark

fn mark(self) -> Mark

The present, to return to with undo_to. Paths are never shortened, so marking changes nothing else.

  • cost: O(1)
  • traps: never

Examples:

  • var d = ParityDsu<0..2>(); let m = d.mark(); d.unite(0, 1); d.undo_to(m); d.diff(0, 1) == None

Source

ParityDsu.undo_to

fn undo_to(mut self, snap: Mark)

Takes back every unite since snap = mark(), contradictions included, newest first.

  • cost: O(1) per undone unite
  • traps: when snap lies after the present (its changes were already undone)

Examples:

  • var d = ParityDsu<0..3>(); d.unite(0, 1); d.unite(1, 2); let m = d.mark(); d.unite(2, 0); d.undo_to(m); d.consistent

Source

PotentialDsu

pub struct PotentialDsu<V>

Weighted (potential / difference-constraint) union-find over domain V with Mark rollback. Maintains constraints of the form val[b] - val[a] == w. All operations are O(log n); mark and consistent are O(1); undo_to is O(1) per undone step.

Source

PotentialDsu.new

fn new<G>(op: ?G = None) -> PotentialDsu<V>

A potential union-find over V with every position alone at the identity potential. Constraints combine with the group operation op, + on Int when it is None.

  • cost: O(n); three [V] arrays
  • traps: never

Examples:

  • let d = PotentialDsu<0..3>(); d.components == 3 and d.consistent

Source

PotentialDsu.find

fn find(self, v: V) -> (root: V, offset: Int)

The representative of v's set and val[v] - val[root].

  • cost: O(log n)
  • ties: None; the representative is fixed by the merges (larger set's root, a's root on equal sizes)
  • traps: never

Examples:

  • var d = PotentialDsu<0..3>(); d.unite(0, 1, 5); d.find(1) == (root: 0, offset: 5)
  • let d = PotentialDsu<0..3>(); d.find(2) == (root: 2, offset: 0)

Source

PotentialDsu.unite

fn unite(mut self, a: V, b: V, w: Int) -> Bool

Records val[b] - val[a] == w.

Returns false when that contradicts what is already known: nothing is merged, the contradiction is counted, and consistent stays false until it is undone. A constraint that is already implied returns true and changes nothing. Merging keeps the larger set's root, a's root on equal sizes.

  • cost: O(log n), plus one log entry when it merges or contradicts
  • traps: never

Examples:

  • var d = PotentialDsu<0..3>(); d.unite(0, 1, 5); d.unite(1, 2, 3); not d.unite(0, 2, 7) and d.unite(0, 2, 8)

Source

PotentialDsu.diff

fn diff(self, a: V, b: V) -> ?Int

val[b] - val[a] when a and b are in the same set, else None.

  • cost: O(log n)
  • traps: never

Examples:

  • var d = PotentialDsu<0..3>(); d.unite(0, 1, 5); d.unite(1, 2, 3); d.diff(0, 2) == Some(8) and d.diff(2, 0) == Some(-8)
  • PotentialDsu<0..3>().diff(0, 1) == None

Source

PotentialDsu.same

fn same(self, a: V, b: V) -> Bool

Whether a and b are in the same set, so that their difference is known.

  • cost: O(log n)
  • traps: never

Examples:

  • var d = PotentialDsu<0..3>(); d.unite(2, 0, 1); d.same(0, 2) and not d.same(0, 1)

Source

PotentialDsu.size

fn size(self, v: V) -> Int

The number of positions in v's set, v included.

  • cost: O(log n)
  • traps: never

Examples:

  • var d = PotentialDsu<0..3>(); d.unite(2, 0, 1); d.size(0) == 2

Source

PotentialDsu.components

fn components(self) -> Int

The number of sets.

  • cost: O(1)
  • traps: never

Examples:

  • var d = PotentialDsu<0..3>(); d.unite(0, 1, 5); d.components == 2

Source

PotentialDsu.consistent

fn consistent(self) -> Bool

Whether no contradiction is in effect.

  • cost: O(1)
  • traps: never

Examples:

  • var d = PotentialDsu<0..2>(); d.unite(0, 1, 5); not d.unite(1, 0, 5) and not d.consistent

Source

PotentialDsu.mark

fn mark(self) -> Mark

The present, to return to with undo_to.

  • cost: O(1)
  • traps: never

Examples:

  • var d = PotentialDsu<0..2>(); let m = d.mark(); d.unite(0, 1, 5); d.undo_to(m); d.diff(0, 1) == None

Source

PotentialDsu.undo_to

fn undo_to(mut self, snap: Mark)

Takes back every unite since snap = mark(), contradictions included, newest first.

  • cost: O(1) per undone unite
  • traps: when snap lies after the present (its changes were already undone)

Examples:

  • var d = PotentialDsu<0..2>(); d.unite(0, 1, 5); let m = d.mark(); d.unite(1, 0, 5); d.undo_to(m); d.consistent and d.diff(0, 1) == Some(5)

Source

RollbackArray

pub struct RollbackArray<D, T>

Domain-indexed array [D]T with Mark rollback. get, set, and mark are O(1); undo_to is O(1) per undone write.

Source

RollbackArray.new

fn new(init: D -> T) -> RollbackArray<D, T>

An array over D holding init(i) at each i, that can step back to any mark.

  • cost: O(n) calls of init, for n = D.count
  • traps: never

Examples:

  • let a = RollbackArray<0..3, Int>(init: i => i * i); a.get(2) == 4

Source

RollbackArray.get

fn get(self, i: D) -> T

The current value at i.

  • cost: O(1)
  • traps: never

Examples:

  • var a = RollbackArray<0..3, Int>(init: i => i); a.set(1, 7); a.get(1) == 7 and a.get(2) == 2

Source

RollbackArray.set

fn set(mut self, i: D, val: T)

Sets i to val, logging the previous value so undo_to can restore it. Every set is logged, marked or not.

  • cost: O(1), plus one log entry
  • traps: never

Examples:

  • var a = RollbackArray<0..2, Int>(init: _ => 0); a.set(0, 5); a.get(0) == 5

Source

RollbackArray.mark

fn mark(self) -> Mark

The present, to return to with undo_to.

  • cost: O(1)
  • traps: never

Examples:

  • var a = RollbackArray<0..2, Int>(init: _ => 0); let m = a.mark(); a.set(1, 3); a.undo_to(m); a.get(1) == 0

Source

RollbackArray.undo_to

fn undo_to(mut self, snap: Mark)

Reverts every set since snap = mark(), newest first, so each position holds what it held at the mark.

  • cost: O(1) per undone set
  • traps: when snap lies after the present (its changes were already undone)

Examples:

  • var a = RollbackArray<0..2, Int>(init: _ => 0); let m = a.mark(); a.set(0, 5); a.set(0, 6); a.undo_to(m); a.get(0) == 0

Source

PersistentDsu

pub struct PersistentDsu<V>

Path-copying persistent disjoint-set union over domain V. Every version remains readable; find, unite, same, and size run in O(log^2 n).

Source

PersistentDsu.new

fn new() -> PersistentDsu<V>

A persistent union-find over V holding version 0, every position in its own set.

  • cost: O(n)
  • traps: never

Examples:

  • let d = PersistentDsu<0..3>(); not d.same(d.base, 0, 1)

Source

PersistentDsu.build

fn build(mut self, lo: Int, hi: Int) -> Int

Source

PersistentDsu.get

fn get(self, root: Int, i: Int) -> (Int, Int)

Source

PersistentDsu.put

fn put(mut self, t: Int, lo: Int, hi: Int, i: Int, cell: (Int, Int)) -> Int

Source

PersistentDsu.root_ord

fn root_ord(self, ver: Int, start: Int) -> Int

Source

PersistentDsu.base

fn base(self) -> Int

The handle of version 0, where every position is alone.

  • cost: O(1)
  • traps: never

Examples:

  • PersistentDsu<0..3>().base == 0

Source

PersistentDsu.find

fn find(self, ver: Int, v: V) -> V

The representative of v's set in version ver, chosen by union by size as in Dsu.find.

  • cost: O(log² n)
  • ties: None; the representative is fixed by the merges (larger set's root, a's root on equal sizes)
  • traps: when ver is not a version handle of self

Examples:

  • var d = PersistentDsu<0..3>(); let v1 = d.unite(d.base, 2, 1); d.find(v1, 1) == 2 and d.find(d.base, 1) == 1

Source

PersistentDsu.same

fn same(self, ver: Int, a: V, b: V) -> Bool

Whether a and b are in the same set in version ver.

  • cost: O(log² n)
  • traps: when ver is not a version handle of self

Examples:

  • var d = PersistentDsu<0..3>(); let v1 = d.unite(d.base, 0, 1); d.same(v1, 0, 1) and not d.same(d.base, 0, 1)

Source

PersistentDsu.size

fn size(self, ver: Int, v: V) -> Int

The number of positions in v's set in version ver, v included.

  • cost: O(log² n)
  • traps: when ver is not a version handle of self

Examples:

  • var d = PersistentDsu<0..3>(); let v1 = d.unite(d.base, 0, 1); d.size(v1, 1) == 2 and d.size(d.base, 1) == 1

Source

PersistentDsu.unite

fn unite(mut self, ver: Int, a: V, b: V) -> Int

A new version equal to ver with the sets of a and b merged; ver itself is unchanged.

Handles are numbered in creation order: the k-th call returns k. A call whose a and b are already one set in ver still returns a fresh handle, equal in content to ver. Merging keeps the larger set's root, a's root on equal sizes.

  • cost: O(log² n) time and O(log n) memory
  • traps: when ver is not a version handle of self

Examples:

  • var d = PersistentDsu<0..3>(); let v1 = d.unite(d.base, 0, 1); let v2 = d.unite(d.base, 1, 2); v1 == 1 and v2 == 2 and d.same(v2, 1, 2) and not d.same(v2, 0, 1)

Source

PersistentDsu.reserve

fn reserve(mut self, nodes: Int)

Preallocates room for at least nodes persistent-array nodes, so later unites do not grow the pool. Changes no version.

  • cost: O(nodes)
  • traps: when nodes < 0

Examples:

  • var d = PersistentDsu<0..3>(); d.reserve(100); d.size(d.base, 0) == 1

Source

On this page