Union-find tracks components as edges arrive
Disjoint-set union maintains a representative for each component. Path compression shortens future finds; union by size prevents repeatedly attaching large trees under small ones.
class DisjointSet(size: Int) {
private val parent = IntArray(size) { it }
private val sizes = IntArray(size) { 1 }
fun find(node: Int): Int {
require(node in parent.indices)
if (parent[node] != node) parent[node] = find(parent[node])
return parent[node]
}
fun union(first: Int, second: Int): Boolean {
var a = find(first)
var b = find(second)
if (a == b) return false
if (sizes[a] < sizes[b]) { val temp = a; a = b; b = temp }
parent[b] = a
sizes[a] += sizes[b]
return true
}
}
A false union result means the vertices were already connected. With both optimizations, amortized cost is near constant, formally involving the inverse Ackermann function. Basic union-find does not support arbitrary edge deletion.
Exercise
Union 0–1 and 1–2, verify 0 and 2 share a representative, then union 0–2 again and expect false.
Check: representatives are implementation details; compare equality of representatives rather than expecting a particular root ID.