Disjoint Set

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(1)	O(n)	O(1)	O(1)

Definition

Short

Disjoint Set is a data structure that allows efficient union and find operations on a set of elements.

Simplified

Disjoint Set is like a smart party organizer. It keeps track of distinct groups (like people at a party), can merge groups, and quickly answer if 2 people belong to the same group. It's a way to manage and query non-overlapping groups efficiently.

Detailed

Disjoint Set, also known as a union-find or merge-find set, is a data structure that manages a collection of elements split into non-overlapping subsets. It enables near-instant operations for creating new sets, merging existing ones, and checking if elements belong to the same set. These operations are crucial in various applications, including Kruskal's algorithm for determining a graph's minimum spanning tree. The speed of these operations is limited by the inverse Ackermann function.

Practice

Practice

Aspect	Pseudo Code
Disjoint Set Item	get_key(): return value get_root(): if is_root(): return this return parent.get_root() is_root(): return parent == ø get_rank(): if length of get_children() == 0: return 0 rank = 0 for each child in get_children(): rank += 1 rank += child.get_rank() return rank get_children(): return values of children set_parent(parent_item, force_setting_parent_child): parent = parent_item if force_setting_parent_child == True: parent_item.add_child(this) add_child(child_item): children[child_item.get_key()] = child_item child_item.set_parent(this, false)
Make Set	make_set(item_value): disjoint_set_item = DisjointSetItem(item_value, keyCallback) if items[disjoint_set_item.get_key()] == ø: items[disjoint_set_item.get_key()] = disjoint_set_item return this
Find	find(item_value): template_disjoint_item = DisjointSetItem(item_value, keyCallback) required_disjoint_item = items[template_disjoint_item.get_key()] if required_disjoint_item == ø: return ø return required_disjoint_item.get_root().get_key()
Union	union(value_a, value_b): root_key_a = find(value_a) root_key_b = find(value_b) if root_key_a == ø or root_key_b == ø: 'One or two values are not in sets' if root_key_a == root_key_b: return this root_a = items[root_key_a] root_b = items[root_key_b] if root_a.get_rank() < root_b.get_rank(): root_b.add_child(root_a) return this root_a.add_child(root_b) return this
In Same Set	in_same_set(value_a, value_b): root_key_a = find(value_a) root_key_b = find(value_b) if root_key_a == ø or root_key_b == ø: 'One or two values are not in sets' return root_key_a == root_key_b

Solution

package main

import (
	"errors"
)

type DisjointSetItem struct {
	value       interface{}
	keyCallback func(interface{}) interface{}
	parent      *DisjointSetItem
	children    map[interface{}]*DisjointSetItem
}

func NewDisjointSetItem(value interface{}, keyCallback func(interface{}) interface{}) *DisjointSetItem {
	return &DisjointSetItem{
		value:       value,
		keyCallback: keyCallback,
		children:    make(map[interface{}]*DisjointSetItem),
	}
}

func (item *DisjointSetItem) GetKey() interface{} {
	if item.keyCallback != nil {
		return item.keyCallback(item.value)
	}
	return item.value
}

func (item *DisjointSetItem) GetRoot() *DisjointSetItem {
	if item.isRoot() {
		return item
	}
	return item.parent.GetRoot()
}

func (item *DisjointSetItem) isRoot() bool {
	return item.parent == nil
}

func (item *DisjointSetItem) GetRank() int {
	if len(item.GetChildren()) == 0 {
		return 0
	}

	rank := 0

	for _, child := range item.GetChildren() {
		rank += 1
		rank += child.GetRank()
	}

	return rank
}

func (item *DisjointSetItem) GetChildren() []*DisjointSetItem {
	children := make([]*DisjointSetItem, 0, len(item.children))
	for _, child := range item.children {
		children = append(children, child)
	}
	return children
}

func (item *DisjointSetItem) SetParent(parentItem *DisjointSetItem, forceSettingParentChild bool) *DisjointSetItem {
	item.parent = parentItem
	if forceSettingParentChild {
		parentItem.AddChild(item)
	}
	return item
}

func (item *DisjointSetItem) AddChild(childItem *DisjointSetItem) *DisjointSetItem {
	item.children[childItem.GetKey()] = childItem
	childItem.SetParent(item, false)
	return item
}

type DisjointSet struct {
	keyCallback func(interface{}) interface{}
	items       map[interface{}]*DisjointSetItem
}

func NewDisjointSet(keyCallback func(interface{}) interface{}) *DisjointSet {
	return &DisjointSet{
		keyCallback: keyCallback,
		items:       make(map[interface{}]*DisjointSetItem),
	}
}

func (ds *DisjointSet) MakeSet(itemValue interface{}) *DisjointSet {
	disjointSetItem := NewDisjointSetItem(itemValue, ds.keyCallback)

	if _, exists := ds.items[disjointSetItem.GetKey()]; !exists {
		ds.items[disjointSetItem.GetKey()] = disjointSetItem
	}

	return ds
}

func (ds *DisjointSet) Find(itemValue interface{}) (interface{}, error) {
	templateDisjointItem := NewDisjointSetItem(itemValue, ds.keyCallback)
	requiredDisjointItem, exists := ds.items[templateDisjointItem.GetKey()]

	if !exists {
		return nil, nil
	}

	return requiredDisjointItem.GetRoot().GetKey(), nil
}

func (ds *DisjointSet) Union(valueA, valueB interface{}) *DisjointSet {
	rootKeyA, errA := ds.Find(valueA)
	rootKeyB, errB := ds.Find(valueB)

	if errA != nil || errB != nil {
		panic(errors.New("One or two values are not in sets"))
	}

	if rootKeyA == rootKeyB {
		return ds
	}

	rootA := ds.items[rootKeyA]
	rootB := ds.items[rootKeyB]

	if rootA.GetRank() < rootB.GetRank() {
		rootB.AddChild(rootA)
		return ds
	}

	rootA.AddChild(rootB)

	return ds
}

func (ds *DisjointSet) InSameSet(valueA, valueB interface{}) (bool, error) {
	rootKeyA, errA := ds.Find(valueA)
	rootKeyB, errB := ds.Find(valueB)

	if errA != nil || errB != nil {
		panic(errors.New("One or two values are not in sets"))
	}

	return rootKeyA == rootKeyB, nil
}

import java.util.HashMap;
import java.util.Map;

class DisjointSetItem<T> {

  private T value;
  private DisjointSetItem<T> parent;
  private Map<T, DisjointSetItem<T>> children;

  public DisjointSetItem(T value) {
    this.value = value;
    this.parent = null;
    this.children = new HashMap<>();
  }

  public T getKey() {
    return this.parent == null ? this.value : this.parent.getKey();
  }

  public DisjointSetItem<T> getRoot() {
    return this.isRoot() ? this : this.parent.getRoot();
  }

  public boolean isRoot() {
    return this.parent == null;
  }

  public int getRank() {
    if (getChildren().isEmpty()) {
      return 0;
    }

    int rank = 0;
    for (DisjointSetItem<T> child : getChildren()) {
      rank += 1;
      rank += child.getRank();
    }

    return rank;
  }

  public Iterable<DisjointSetItem<T>> getChildren() {
    return children.values();
  }

  public DisjointSetItem<T> setParent(DisjointSetItem<T> parentItem, boolean forceSettingParentChild) {
    this.parent = parentItem;
    if (forceSettingParentChild) {
      parentItem.addChild(this);
    }

    return this;
  }

  public DisjointSetItem<T> addChild(DisjointSetItem<T> childItem) {
    children.put(childItem.getKey(), childItem);
    childItem.setParent(this, false);

    return this;
  }
}

public class DisjointSet<T> {

  private Map<T, DisjointSetItem<T>> items;
  private KeyCallback<T> keyCallback;

  public DisjointSet(KeyCallback<T> keyCallback) {
    this.keyCallback = keyCallback;
    this.items = new HashMap<>();
  }

  public DisjointSet<T> makeSet(T itemValue) {
    DisjointSetItem<T> disjointSetItem = new DisjointSetItem<>(itemValue);

    if (!items.containsKey(disjointSetItem.getKey())) {
      items.put(disjointSetItem.getKey(), disjointSetItem);
    }

    return this;
  }

  public T find(T itemValue) {
    DisjointSetItem<T> templateDisjointItem = new DisjointSetItem<>(itemValue);
    DisjointSetItem<T> requiredDisjointItem = items.get(templateDisjointItem.getKey());

    if (requiredDisjointItem == null) {
      return null;
    }

    return requiredDisjointItem.getRoot().getKey();
  }

  public DisjointSet<T> union(T valueA, T valueB) {
    T rootKeyA = find(valueA);
    T rootKeyB = find(valueB);

    if (rootKeyA == null || rootKeyB == null) {
      throw new RuntimeException("One or two values are not in sets");
    }

    if (rootKeyA.equals(rootKeyB)) {
      return this;
    }

    DisjointSetItem<T> rootA = items.get(rootKeyA);
    DisjointSetItem<T> rootB = items.get(rootKeyB);

    if (rootA.getRank() < rootB.getRank()) {
      rootB.addChild(rootA);
      return this;
    }

    rootA.addChild(rootB);

    return this;
  }

  public boolean inSameSet(T valueA, T valueB) {
    T rootKeyA = find(valueA);
    T rootKeyB = find(valueB);

    if (rootKeyA == null || rootKeyB == null) {
      throw new RuntimeException("One or two values are not in sets");
    }

    return rootKeyA.equals(rootKeyB);
  }

  public interface KeyCallback<T> {

    T getKey(T value);
  }
}

class DisjointSetItem {
  constructor(value, keyCallback) {
    this.value = value;
    this.keyCallback = keyCallback;
    this.parent = null;
    this.children = {};
  }

  getKey() {
    if (this.keyCallback) {
      return this.keyCallback(this.value);
    }
    return this.value;
  }

  getRoot() {
    return this.isRoot() ? this : this.parent.getRoot();
  }

  isRoot() {
    return this.parent === null;
  }

  getRank() {
    if (this.getChildren().length === 0) {
      return 0;
    }

    let rank = 0;

    this.getChildren().forEach((child) => {
      rank += 1;
      rank += child.getRank();
    });

    return rank;
  }

  getChildren() {
    return Object.values(this.children);
  }

  setParent(parentItem, forceSettingParentChild = true) {
    this.parent = parentItem;
    if (forceSettingParentChild) {
      parentItem.addChild(this);
    }

    return this;
  }

  addChild(childItem) {
    this.children[childItem.getKey()] = childItem;
    childItem.setParent(this, false);

    return this;
  }
}

class DisjointSet {
  constructor(keyCallback) {
    this.keyCallback = keyCallback;
    this.items = {};
  }

  makeSet(itemValue) {
    const disjointSetItem = new DisjointSetItem(itemValue, this.keyCallback);

    if (!this.items[disjointSetItem.getKey()]) {
      this.items[disjointSetItem.getKey()] = disjointSetItem;
    }

    return this;
  }

  find(itemValue) {
    const templateDisjointItem = new DisjointSetItem(
      itemValue,
      this.keyCallback,
    );
    const requiredDisjointItem = this.items[templateDisjointItem.getKey()];

    if (!requiredDisjointItem) {
      return null;
    }

    return requiredDisjointItem.getRoot().getKey();
  }

  union(valueA, valueB) {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (rootKeyA === null || rootKeyB === null) {
      throw new Error("One or two values are not in sets");
    }

    if (rootKeyA === rootKeyB) {
      return this;
    }

    const rootA = this.items[rootKeyA];
    const rootB = this.items[rootKeyB];

    if (rootA.getRank() < rootB.getRank()) {
      rootB.addChild(rootA);
      return this;
    }

    rootA.addChild(rootB);

    return this;
  }

  inSameSet(valueA, valueB) {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (rootKeyA === null || rootKeyB === null) {
      throw new Error("One or two values are not in sets");
    }

    return rootKeyA === rootKeyB;
  }
}

data class DisjointSetItem<T>(
        val value: T,
        val keyCallback: ((T) -> T)? = null,
        var parent: DisjointSetItem<T>? = null,
        val children: MutableMap<T, DisjointSetItem<T>> = mutableMapOf()
) {
    fun getKey(): T {
        return parent?.getKey() ?: keyCallback?.invoke(value) ?: value
    }

    fun getRoot(): DisjointSetItem<T> {
        return if (isRoot()) this else parent!!.getRoot()
    }

    fun isRoot(): Boolean {
        return parent == null
    }

    fun getRank(): Int {
        return if (getChildren().isEmpty()) {
            0
        } else {
            getChildren().sumBy {
                1 + it.getRank()
            }
        }
    }

    fun getChildren(): Collection<DisjointSetItem<T>> {
        return children.values
    }

    fun setParent(parentItem: DisjointSetItem<T>, forceSettingParentChild: Boolean = true): DisjointSetItem<T> {
        parent = parentItem
        if (forceSettingParentChild) {
            parentItem.addChild(this)
        }
        return this
    }

    fun addChild(childItem: DisjointSetItem<T>): DisjointSetItem<T> {
        children[childItem.getKey()] = childItem
        childItem.setParent(this, false)
        return this
    }
}

class DisjointSet<T>(private val keyCallback: ((T) -> T)? = null) {
    private val items: MutableMap<T, DisjointSetItem<T>> = mutableMapOf()

    fun makeSet(itemValue: T): DisjointSet<T> {
        val disjointSetItem = DisjointSetItem(itemValue, keyCallback)

        if (!items.containsKey(disjointSetItem.getKey())) {
            items[disjointSetItem.getKey()] = disjointSetItem
        }

        return this
    }

    fun find(itemValue: T): T? {
        val templateDisjointItem = DisjointSetItem(itemValue, keyCallback)
        val requiredDisjointItem = items[templateDisjointItem.getKey()]

        return requiredDisjointItem?.getRoot()?.getKey()
    }

    fun union(valueA: T, valueB: T): DisjointSet<T> {
        val rootKeyA = find(valueA)
        val rootKeyB = find(valueB)

        if (rootKeyA == null || rootKeyB == null) {
            throw RuntimeException("One or two values are not in sets")
        }

        if (rootKeyA == rootKeyB) {
            return this
        }

        val rootA = items[rootKeyA]!!
        val rootB = items[rootKeyB]!!

        if (rootA.getRank() < rootB.getRank()) {
            rootB.addChild(rootA)
        } else {
            rootA.addChild(rootB)
        }

        return this
    }

    fun inSameSet(valueA: T, valueB: T): Boolean {
        val rootKeyA = find(valueA)
        val rootKeyB = find(valueB)

        if (rootKeyA == null || rootKeyB == null) {
            throw RuntimeException("One or two values are not in sets")
        }

        return rootKeyA == rootKeyB
    }
}

class DisjointSetItem:
    def __init__(self, value, key_callback=None):
        self.value = value
        self.key_callback = key_callback
        self.parent = None
        self.children = {}

    def get_key(self):
        if self.key_callback:
            return self.key_callback(self.value)
        return self.value

    def get_root(self):
        return self if self.is_root() else self.parent.get_root()

    def is_root(self):
        return self.parent is None

    def get_rank(self):
        if not self.get_children():
            return 0

        rank = 0
        for child in self.get_children():
            rank += 1
            rank += child.get_rank()

        return rank

    def get_children(self):
        return list(self.children.values())

    def set_parent(self, parent_item, force_setting_parent_child=True):
        self.parent = parent_item
        if force_setting_parent_child:
            parent_item.add_child(self)
        return self

    def add_child(self, child_item):
        self.children[child_item.get_key()] = child_item
        child_item.set_parent(self, False)
        return self


class DisjointSet:
    def __init__(self, key_callback=None):
        self.key_callback = key_callback
        self.items = {}

    def make_set(self, item_value):
        disjoint_set_item = DisjointSetItem(item_value, self.key_callback)

        if disjoint_set_item.get_key() not in self.items:
            self.items[disjoint_set_item.get_key()] = disjoint_set_item

        return self

    def find(self, item_value):
        template_disjoint_item = DisjointSetItem(item_value, self.key_callback)
        required_disjoint_item = self.items.get(template_disjoint_item.get_key())

        if not required_disjoint_item:
            return None

        return required_disjoint_item.get_root().get_key()

    def union(self, value_a, value_b):
        root_key_a = self.find(value_a)
        root_key_b = self.find(value_b)

        if root_key_a is None or root_key_b is None:
            raise ValueError("One or two values are not in sets")

        if root_key_a == root_key_b:
            return self

        root_a = self.items[root_key_a]
        root_b = self.items[root_key_b]

        if root_a.get_rank() < root_b.get_rank():
            root_b.add_child(root_a)
        else:
            root_a.add_child(root_b)

        return self

    def in_same_set(self, value_a, value_b):
        root_key_a = self.find(value_a)
        root_key_b = self.find(value_b)

        if root_key_a is None or root_key_b is None:
            raise ValueError("One or two values are not in sets")

        return root_key_a == root_key_b

use std::collections::HashMap;

struct DisjointSetItem<T> {
    value: T,
    key_callback: Option<Box<dyn Fn(&T) -> String>>,
    parent: Option<Box<DisjointSetItem<T>>>,
    children: HashMap<String, Box<DisjointSetItem<T>>>,
}

impl<T> DisjointSetItem<T> {
    fn new(value: T, key_callback: Option<Box<dyn Fn(&T) -> String>>) -> Self {
        DisjointSetItem {
            value,
            key_callback,
            parent: None,
            children: HashMap::new(),
        }
    }

    fn get_key(&self) -> String {
        if let Some(callback) = &self.key_callback {
            callback(&self.value)
        } else {
            format!("{:?}", &self.value)
        }
    }

    fn get_root(&self) -> &DisjointSetItem<T> {
        if self.is_root() {
            self
        } else {
            self.parent.as_ref().unwrap().get_root()
        }
    }

    fn is_root(&self) -> bool {
        self.parent.is_none()
    }

    fn get_rank(&self) -> usize {
        if self.get_children().is_empty() {
            0
        } else {
            self.get_children().len() + self.get_children().iter().map(|child| child.get_rank()).sum::<usize>()
        }
    }

    fn get_children(&self) -> Vec<&DisjointSetItem<T>> {
        self.children.values().map(|child| child.as_ref()).collect()
    }

    fn set_parent(&mut self, parent_item: Box<DisjointSetItem<T>>, force_setting_parent_child: bool) {
        self.parent = Some(parent_item);
        if force_setting_parent_child {
            self.parent.as_mut().unwrap().add_child(Box::new(self.clone()));
        }
    }

    fn add_child(&mut self, child_item: Box<DisjointSetItem<T>>) {
        self.children.insert(child_item.get_key(), child_item);
    }
}

struct DisjointSet<T> {
    key_callback: Option<Box<dyn Fn(&T) -> String>>,
    items: HashMap<String, Box<DisjointSetItem<T>>>,
}

impl<T> DisjointSet<T> {
    fn new(key_callback: Option<Box<dyn Fn(&T) -> String>>) -> Self {
        DisjointSet {
            key_callback,
            items: HashMap::new(),
        }
    }

    fn make_set(&mut self, item_value: T) {
        let disjoint_set_item = Box::new(DisjointSetItem::new(item_value, self.key_callback.clone()));

        if !self.items.contains_key(&disjoint_set_item.get_key()) {
            self.items.insert(disjoint_set_item.get_key(), disjoint_set_item);
        }
    }

    fn find(&self, item_value: T) -> Option<String> {
        let template_disjoint_item = Box::new(DisjointSetItem::new(item_value, self.key_callback.clone()));
        if let Some(required_disjoint_item) = self.items.get(&template_disjoint_item.get_key()) {
            Some(required_disjoint_item.get_root().get_key())
        } else {
            None
        }
    }

    fn union(&mut self, value_a: T, value_b: T) -> Result<(), &'static str> {
        let root_key_a = self.find(value_a).ok_or("One or two values are not in sets")?;
        let root_key_b = self.find(value_b).ok_or("One or two values are not in sets")?;

        if root_key_a == root_key_b {
            return Ok(());
        }

        let root_a = self.items.get_mut(&root_key_a).unwrap();
        let root_b = self.items.get_mut(&root_key_b).unwrap();

        if root_a.get_rank() < root_b.get_rank() {
            root_b.add_child(Box::new(root_a.clone()));
        } else {
            root_a.add_child(Box::new(root_b.clone()));
        }

        Ok(())
    }

    fn in_same_set(&self, value_a: T, value_b: T) -> Result<bool, &'static str> {
        let root_key_a = self.find(value_a).ok_or("One or two values are not in sets")?;
        let root_key_b = self.find(value_b).ok_or("One or two values are not in sets")?;

        Ok(root_key_a == root_key_b)
    }
}

class DisjointSetItem<T> {
  value: T;
  keyCallback: ((value: T) => string) | undefined;
  parent: DisjointSetItem<T> | null;
  children: { [key: string]: DisjointSetItem<T> };

  constructor(value: T, keyCallback?: (value: T) => string) {
    this.value = value;
    this.keyCallback = keyCallback;
    this.parent = null;
    this.children = {};
  }

  getKey(): string {
    if (this.keyCallback) {
      return this.keyCallback(this.value);
    }
    return String(this.value);
  }

  getRoot(): DisjointSetItem<T> {
    return this.isRoot() ? this : this.parent!.getRoot();
  }

  isRoot(): boolean {
    return this.parent === null;
  }

  getRank(): number {
    if (this.getChildren().length === 0) {
      return 0;
    }

    let rank = 0;

    this.getChildren().forEach((child) => {
      rank += 1;
      rank += child.getRank();
    });

    return rank;
  }

  getChildren(): DisjointSetItem<T>[] {
    return Object.values(this.children);
  }

  setParent(
    parentItem: DisjointSetItem<T>,
    forceSettingParentChild: boolean = true,
  ): this {
    this.parent = parentItem;
    if (forceSettingParentChild) {
      parentItem.addChild(this);
    }

    return this;
  }

  addChild(childItem: DisjointSetItem<T>): this {
    this.children[childItem.getKey()] = childItem;
    childItem.setParent(this, false);

    return this;
  }
}

class DisjointSet<T> {
  keyCallback: ((value: T) => string) | undefined;
  items: { [key: string]: DisjointSetItem<T> };

  constructor(keyCallback?: (value: T) => string) {
    this.keyCallback = keyCallback;
    this.items = {};
  }

  makeSet(itemValue: T): this {
    const disjointSetItem = new DisjointSetItem(itemValue, this.keyCallback);

    if (!this.items[disjointSetItem.getKey()]) {
      this.items[disjointSetItem.getKey()] = disjointSetItem;
    }

    return this;
  }

  find(itemValue: T): string | null {
    const templateDisjointItem = new DisjointSetItem(
      itemValue,
      this.keyCallback,
    );
    const requiredDisjointItem = this.items[templateDisjointItem.getKey()];

    if (!requiredDisjointItem) {
      return null;
    }

    return requiredDisjointItem.getRoot().getKey();
  }

  union(valueA: T, valueB: T): this {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (rootKeyA === null || rootKeyB === null) {
      throw new Error("One or two values are not in sets");
    }

    if (rootKeyA === rootKeyB) {
      return this;
    }

    const rootA = this.items[rootKeyA];
    const rootB = this.items[rootKeyB];

    if (rootA.getRank() < rootB.getRank()) {
      rootB.addChild(rootA);
    } else {
      rootA.addChild(rootB);
    }

    return this;
  }

  inSameSet(valueA: T, valueB: T): boolean {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (rootKeyA === null || rootKeyB === null) {
      throw new Error("One or two values are not in sets");
    }

    return rootKeyA === rootKeyB;
  }
}