Union Find (Disjoint Set)

Union Find is a data structure that keeps track of elements which are partitioned into disjoint sets (for example, connected components of a graph). It provides operations to union existing sets, and find the set to which a particular element belongs. Each set is represented by a unique identifier, and this identifier is root of tree with all elements in the set as its vertices. It is commonly used in network connectivity, image processing, and clustering algorithms.

Rust Implementation

struct UnionFind<F>
where F: Fn(usize, usize) -> usize
{
    root: Vec<usize>,
    size: Vec<usize>,
    components: usize,
    character: Vec<usize>,
    op: F,
}

impl<F> UnionFind<F>
where F: Fn(usize, usize) -> usize
{
    pub fn new(n: usize, op: F, init: usize) -> Self {
        Self {
            root: (0..=n).collect(),
            size: vec![1; n + 1],
            components: n,
            character: vec![init; n + 1],
            op,
        }
    }

    pub fn find(&mut self, x: usize) -> usize {
        if self.root[x] == x { return x }
        self.root[x] = self.find(self.root[x]);
        self.root[x]
    }

    pub fn union(&mut self, x: usize, y: usize, w: usize) -> bool {
        let root_x = self.find(x);
        let root_y = self.find(y);

        if root_x == root_y {
            self.character[root_x] = (self.op)(self.character[root_x], w);
            return false;
        }

        if self.size[root_x] > self.size[root_y] {
            self.size[root_x] += self.size[root_y];
            self.character[root_x] = (self.op)((self.op)(self.character[root_x], self.character[root_y]), w);
            self.root[root_y] = root_x;
        } else {
            self.size[root_y] += self.size[root_x];
            self.character[root_y] = (self.op)((self.op)(self.character[root_x], self.character[root_y]), w);
            self.root[root_x] = root_y;
        }
        self.components -= 1;
        true
    }

    pub fn are_connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }

    pub fn get_components(&self) -> usize {
        self.components
    }

    pub fn get_root(&mut self, x: usize) -> usize {
        self.find(x)
    }

    pub fn get_character(&mut self, x: usize) -> usize {
        let root_x = self.find(x);
        self.character[root_x]
    }

    pub fn get_size(&mut self, x: usize) -> usize {
        let root_x = self.find(x);
        self.size[root_x]
    }
}

Python Implementation

class UnionFind(n: int, vertices=None)

Bases: object

Union-Find data structure

Variant with size of component attribute (for optimization) and number of components attribute

are_connected(x: int, y: int) → bool

Check if the given nodes are connected

Time complexity: \(O(a(n))\), where a(n) is the inverse Ackermann function (very slow growing function).

Space complexity: \(O(1)\)

find(x: int) → int

Find the parent of the given node.

Time complexity: \(O(a(n))\)

Space complexity: \(O(1)\)

union(x: int, y: int) → int

Union the components that the given nodes belong to.

Time complexity: \(O(a(n))\), where a(n) is the inverse Ackermann function (very slow growing function).

Space complexity: \(O(1)\)

class UnionFindSimple(size)

Bases: object

Union-Find

Variant without rank attribute (for simplicity)

are_connected(x, y)

find(x)

union(x, y)