UnionFind in rustc_data_structures::union_find - Rust (original) (raw)

pub struct UnionFind<Key: Idx> {
    table: IndexVec<Key, UnionFindEntry<Key>>,
}

Expand description

Simple implementation of a union-find data structure, i.e. a disjoint-set forest.

Source§

Source

Creates a new disjoint-set forest containing the keys 0..num_keys. Initially, every key is part of its own one-element set.

Source

Returns the “root” key of the disjoint-set containing the given key. If two keys have the same root, they belong to the same set.

Also updates internal data structures to make subsequent findoperations faster.

Source

Merges the set containing a and the set containing b into one set.

Returns the common root of both keys, after the merge.

Source

Takes a “snapshot” of the current state of this disjoint-set forest, in the form of a vector that directly maps each key to its current root.

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 24 bytes