The RAW union find (disjoint set) library
npm install @rawify/unionfind
UnionFind.js is a optimized implementation of the Union–Find (Disjoint Set Union) data structure for JavaScript.
It supports union by size and path halving for near-constant-time performance in practical use cases.
- Union–Find / Disjoint Set Union with union by size and path halving
- Single Int32Array storage for maximum memory efficiency
- Amortized O(α(N)) performance (inverse Ackermann function)
- Zero allocations in hot paths
- reset() method for instant reuse without GC churn
- Works in Node.js and browsers
You can install UnionFind.js via npm:
``bash`
npm install @rawify/unionfind
Or with yarn:
`bash`
yarn add @rawify/unionfind
Alternatively, download or clone the repository:
`bash`
git clone https://github.com/rawify/UnionFind.js
In Node.js:
`javascript`
const UnionFind = require('@rawify/unionfind');
Or ES modules:
`javascript`
import UnionFind from '@rawify/unionfind';
`javascript`
// Create a UnionFind for elements 0..9
let uf = new UnionFind(10);
Finds the representative (root) of the set containing x.
`javascript`
uf.find(3); // returns root index of set containing 3
Merges the sets containing a and b. Returns true if merged, false if already in the same set.
`javascript`
uf.union(1, 2); // merges sets containing 1 and 2
Checks whether a and b are in the same set.
`javascript`
uf.connected(1, 2); // true
Returns the size of the set containing x.
`javascript`
uf.sizeOf(1); // 3
Returns the number of disjoint sets.
`javascript`
uf.count(); // 7
Resets the structure to all singletons without reallocating.
`javascript`
uf.reset();
Returns the number of elements tracked.
`javascript`
uf.length; // 10
`javascript
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(3, 4);
console.log(uf.connected(0, 1)); // true
console.log(uf.connected(1, 2)); // false
console.log(uf.sizeOf(0)); // 2
console.log(uf.count()); // 3
uf.union(1, 4);
console.log(uf.connected(0, 3)); // true
`
* Typed arrays keep memory compact and make find/union JIT-friendly.reset()
* Path halving improves cache locality and minimizes pointer chasing.
* Avoids per-call allocations for maximum throughput in tight loops.
* Use to reuse the structure without creating garbage.
As with every library I publish, UnionFind.js is written to be as small and efficient as possible after compression with Google Closure Compiler in advanced mode. Please preserve this style if you plan to extend the library.
After cloning the Git repository run:
`
npm install
npm run build
Testing the source against the shipped test suite is as easy as:
`
npm run test
Copyright (c) 2025, Robert Eisele
Licensed under the MIT license.