Disjoint Set Union

Implementations

C++

// for the single array holds size and par trick
// you need a signed int as the array elem type
// since the par too must be same as the elem type
// you need int as type
// templating here is kind of wasteful
 
#include <vector>
 
class DSU {
  private:
	std::vector<int> par_;
 
  public:
	// all are their root and have size 1
	DSU(int size) : par_(size, -1) {};
 
	int root(int elem) {
		if (par_[elem] < 0)
			return elem;
		return par_[elem] = root(par_[elem]);
	}
 
	void merge(int a, int b) {
		if ((a = root(a)) == (b = root(b)))
			return;
 
		// aim is to keep the height small and if assume more elems = prob more
		// height then you would want to attach the smaller one below the larger
		// one INFO: larger one dominates
 
		// invariant: a is larger
		if (-par_[a] < -par_[b])
			std::swap(a, b);
 
		par_[a] += par_[b];
		par_[b] = a;
	}
};

Java

import java.util.Arrays;
 
final class DSU {
    private int[] par;
 
    DSU(int size) {
        par = new int[size];
        Arrays.fill(par, -1);
    }
 
    public int root(int elem) {
        if (par[elem] < 0)
            return elem;
        return par[elem] = root(par[elem]);
    }
 
    public void merge(int a, int b) {
        if ((a = root(a)) == (b = root(b))) {
            return;
        }
 
        // invariant: a is larger
        if (-par[a] < -par[b]) {
            // NOTE: the one liner arcane swap
            a = a ^ b ^ (b = a);
        }
 
        par[a] += par[b];
        par[b] = a;
    }
}

Notes

java swap trick

for primitive integral types only like int and long

a = a ^ b ^ ( b = a );

can’t use with object references, for those you need a temp