Union Find
Updated: 01 February 2024
Used to work with the problem of connecting objects and determining if those two objects are connected
Refers to the problem when given a set of objects N to be able to:
 Union  Connect two objects
 Connected  Check if a path that connects two objects exists
e.g. Given some set of items that are connected in a network
01 2 34


5 67 89
In the above example we have some items that are connected. In the above set we can ask a question like “Is 3 connected to 9”
Implementation
In the implementation of the Union Find we will use a UnionFind
data type that has union
and connected
methods
algorithms/unionfind/interface.ts
export interface UnionFind {
connected(a: number, b: number): boolean;
union(a: number, b: number): void;
}
Quick Find
An implementation can be seen below:
algorithms/unionfind/quickfind.ts
import type { UnionFind } from "./interface";
export class QuickFind implements UnionFind {
/*
* Track the group associated with each item based on its index
*/
groups: number[];
/* Initially each item is identified by a group
* that is the same as its own index
*/
constructor(size: number) {
this.groups = new Array(size).fill(0).map((_, i) => i);
}
/*
* If two items are connected their groups will be the same
*/
connected(a: number, b: number) {
const groupA = this.groups[a];
const groupB = this.groups[b];
return groupA === groupB;
}
/*
* Joins two items by setting all items of the one group
* to the same as the other group
*/
union(a: number, b: number) {
const groupA = this.groups[a];
const groupB = this.groups[b];
/*
* Iterate through each item and if they are the same as B
* then update them to be A
*/
for (let index = 0; index < this.groups.length; index++) {
const group = this.groups[index];
if (group === groupB) {
this.groups[index] = groupA;
}
}
}
}
Quick Union
Quick union is an implementation of union find that uses a tree to represent the data structure. In this implementation instead of storing the representative group we store the connections as a forest where each connected set is a tree
algorithms/unionfind/quickunion.ts
export class QuickUnion {
/*
* Track the parent associated with each items.
* The element is a root node if the parent is the same as the node
*/
parents: number[];
/* Initially each item is identified by a parent
* that is the same as its own index
*/
constructor(size: number) {
this.parents = new Array(size).fill(0).map((_, i) => i);
}
/*
* Get the root of a given node
*/
root(a: number) {
let parent = a;
while (parent !== this.parents[a]) {
parent = this.parents[parent];
}
return parent;
}
/*
* If two items have the same root they are connected
*/
connected(a: number, b: number) {
return this.root(a) === this.root(b);
}
/*
* Joins a node by setting its root to that of the other node
*/
union(a: number, b: number) {
const root = this.root(a);
this.parents[b] = root;
}
}
Weighted Quick Union
What slows down the quick union is traversing up through a long tree. THe idea here is to avoid tall trees, to do this we need to:
 Keep track of size of each tree (number of objects)
 Balance by linking root of smaller tree to root of larger tree
algorithms/unionfind/weightedquickunion.ts
import type { UnionFind } from "./interface";
export class WeightedQuickUnion implements UnionFind {
/*
* Track the parent associated with each items.
* The element is a root node if the parent is the same as the node
*/
parents: number[];
/*
* The number of elements in each tree
*/
sizes: number[];
/* Initially each item is identified by a parent
* that is the same as its own index
*/
constructor(size: number) {
this.parents = new Array(size).fill(0).map((_, i) => i);
this.sizes = new Array(size).fill(1);
}
/*
* Get the root of a given node
*/
root(a: number) {
let parent = a;
while (parent !== this.parents[a]) {
parent = this.parents[parent];
}
return parent;
}
/*
* If two items have the same root they are connected
*/
connected(a: number, b: number) {
return this.root(a) === this.root(b);
}
/*
* Joins a node by setting its root to that of the other node
*
* Differs from Quick Union by checking tree sizes and prefering a
* smaller tree where possible
*/
union(a: number, b: number) {
const rootA = this.root(a);
const rootB = this.root(b);
if (rootA === rootB) {
return;
}
const sizeA = this.sizes[rootA];
const sizeJ = this.sizes[rootB];
if (sizeA < sizeJ) {
this.parents[rootA] = rootB;
this.sizes[rootB] += sizeA;
} else {
this.parents[rootB] = rootA;
this.sizes[rootA] += sizeJ;
}
}
}
For this algorithm the depth of any node should be at most lg N
(lg is shorthand for Log with base 2)
Weighted Quick Union with Path Compression
By modifying the implementation to update the root of any item we read as we read it we can save a lot of read iterations in the future by updating each nonroot node to move it a level up when we read it:
algorithms/unionfind/weightedquickunionpathcomp.ts
import type { UnionFind } from "./interface";
export class WeightedQuickUnionPathCompression implements UnionFind {
/*
* Track the parent associated with each items.
* The element is a root node if the parent is the same as the node
*/
parents: number[];
/*
* The number of elements in each tree
*/
sizes: number[];
/* Initially each item is identified by a parent
* that is the same as its own index
*/
constructor(size: number) {
this.parents = new Array(size).fill(0).map((_, i) => i);
this.sizes = new Array(size).fill(1);
}
/*
* Get the root of a given node
*/
root(a: number) {
let parent = a;
while (parent !== this.parents[parent]) {
// since we're already at this node we can just move it up a level
parent = this.parents[this.parents[parent]];
this.parents[parent] = parent;
}
return parent;
}
/*
* If two items have the same root they are connected
*/
connected(a: number, b: number) {
return this.root(a) === this.root(b);
}
/*
* Joins a node by setting its root to that of the other node
*
* Differs from Quick Union by checking tree sizes and prefering a
* smaller tree where possible
*/
union(a: number, b: number) {
const rootA = this.root(a);
const rootB = this.root(b);
if (rootA === rootB) {
return;
}
const sizeA = this.sizes[rootA];
const sizeB = this.sizes[rootB];
if (sizeA < sizeB) {
this.parents[rootA] = rootB;
this.sizes[rootB] += sizeA;
} else {
this.parents[rootB] = rootA;
this.sizes[rootA] += sizeB;
}
}
}
Since we have flattened the tree at every pass the union time of this agorithm makes it less than N + M lg* N
(lg* is a super small value)
Complexity
algorithm  init  union  find 

quickfind  N  N  1 
quickunion  N  N (note)  N 
weightedquickunion  N  lg N (note)  lg N 
weightedquickunionpc  N  lg* N  lg N 
(note) Includes cost of finding the root