disjoint set in rust

Disjoint Set is a data structure that allows us to keep track of disjoint sets and perform operations such as union and find efficiently. In Rust, we can implement Disjoint Set using the Union-Find algorithm.

Here is an implementation of Disjoint Set using the rust-lang library:


main.rs
use std::collections::HashMap;

struct DisjointSet {
    parent: HashMap<i32, i32>,
    rank: HashMap<i32, i32>,
}

impl DisjointSet {
    fn new() -> Self {
        DisjointSet {
            parent: HashMap::new(),
            rank: HashMap::new(),
        }
    }

    fn make_set(&mut self, i: i32) {
        if !self.parent.contains_key(&i) {
            self.parent.insert(i, i);
            self.rank.insert(i, 0);
        }
    }

    fn find(&mut self, i: i32) -> i32 {
        if !self.parent.contains_key(&i) {
            return -1;
        }
        if self.parent[&i] != i {
            self.parent.insert(i, self.find(self.parent[&i]));
        }
        return self.parent[&i];
    }

    fn union(&mut self, i: i32, j: i32) {
        let i_root = self.find(i);
        let j_root = self.find(j);
        if i_root == j_root {
            return;
        }
        if self.rank[&i_root] < self.rank[&j_root] {
            self.parent.insert(i_root, j_root);
        } else if self.rank[&i_root] > self.rank[&j_root] {
            self.parent.insert(j_root, i_root);
        } else {
            self.parent.insert(j_root, i_root);
            self.rank.insert(i_root, self.rank[&i_root] + 1);
        }
    }
}
1226 chars
49 lines

To use this implementation, we can create a new instance of the Disjoint Set using the new method. We can then add elements to the set using the make_set method. We can perform the find operation using the find method, and the union operation using the union method.

Here is an example usage:


main.rs
fn main() {
    let mut ds = DisjointSet::new();
    ds.make_set(1);
    ds.make_set(2);
    ds.union(1, 2);
    assert_eq!(ds.find(1), ds.find(2));
}
151 chars
8 lines

similar rust code snippets

insert an element into an array at a specific index in rust

remove an element from an array at a specific index in rust

remove an element from the middle of an array in rust

find the index of an element in an array in rust

sort an array in rust

remove an element from the beginning of an array in rust

add an element to the beginning of an array in rust

add an element to the end of an array in rust

remove an element from the end of an array in rust

reverse an array in rust

related categories