Incremental Connectivity Tracking with Union-Find

Union-Find, also known as Disjoint Set Union, is a data structure that tracks which connected component each element belongs to. Initially every element is its own independent set; union(a, b) merges two sets, and find(a) returns the canonical root (representative) of the set containing a given element.

Linking only parent pointers can produce long chains depending on input order. This implementation combines union-by-size, which attaches a smaller tree under a larger one, with path halving, which pulls intermediate nodes toward their grandparents while locating the root.
Including the cost of element creation, building N elements and performing m operations costs O(N + m α(N)).
If element creation is counted within m, or if we assume m ≥ N, this is typically written as O(m α(N)). The amortized cost per operation is O(α(N)), which does not mean every individual operation is always O(1) in the worst case.

To be precise about the source of the inverse Ackermann amortized bound: Tarjan's 1975 result analyzed the combination of path compression and union-by-size.¹
The path halving used here was not the subject of analysis in that paper,
and Tarjan and van Leeuwen later showed that each combination of union-by-size or rank with compression, splitting, and halving achieves the same asymptotic bound.² (Honestly, this statement still confuses me, but that is what the paper says.)

The real advantage of this structure is that it answers connectivity queries using just two compact integer arrays, rather than repeatedly traversing an entire graph object. It is well suited for problems where connections are only ever added, such as network endpoint tracking, image region labeling, account merge candidates, and Kruskal's minimum spanning tree algorithm.

The trade-off here is limited functionality. Union-Find tells you whether two elements are connected, but it does not tell you the actual path between them.

It also cannot directly handle situations where deleting an edge splits a component. When deletions are required, you need either a full rebuild, offline processing with a Rollback DSU, or a dynamic connectivity data structure.

Loading animated diagram...

Text

Union-Find
= Parent Forest
+ Union-by-Size
+ Path Halving

find(x)
= root of the set containing x

union(a, b)
if root(a) and root(b) differ
  attach the smaller component under the larger component

connected(a, b)
= find(a) == find(b)

Core invariants:

elements that are roots:
parent[root] == root

all elements:
following parent pointers repeatedly leads to
exactly one root

componentSize[root]
= number of elements represented by that root

1. Problem Setup

Consider a network management system where connection information between servers arrives sequentially.

Text

Server:
0, 1, 2, 3, 4, 5

New connection:
0 — 1
1 — 2
3 — 4
2 — 4

Initially, every server is an independent component.

Text

{0} {1} {2} {3} {4} {5}

After applying 0—1 and 1—2, the state looks like this.

Text

{0, 1, 2} {3} {4} {5}

After applying 3—4, the state looks like this.

Text

{0, 1, 2} {3, 4} {5}

Finally, applying 2—4 merges the two components.

Text

{0, 1, 2, 3, 4} {5}

The essential requirements:

Text

Are 0 and 4 connected?
→ true

Are 0 and 5 connected?
→ false

What is the size of the component containing 3?
→ 5

How many independent components are there currently?
→ 2

This implementation assumes element IDs are dense integers in the range 0..N-1. UUID or string-based IDs should be converted to integer indexes at the call boundary.

2. Core Representation

Error Handling

The public API in this document does not throw exceptions for failures that the caller can handle, such as invalid element counts, out-of-range node indices, unknown external server IDs, or snapshot loading errors. Each implementation uses an exclusive Result-style type that carries either a success value T or an error value.

TypeScript makes the error type E generic as well, while the C++, Python, and C# examples use DisjointSetError as a fixed error type.
Construction is exposed only through a create or Create factory, and a failed construction never produces an empty or partially initialized object.

A false return from connect() is not an error; it is the normal result indicating that two nodes were already in the same component. By contrast, invalid-node and invalid-element-count are explicit failures that require the caller to correct its input or reject the request. Memory exhaustion, defects in the runtime itself, and violations of private helper preconditions are not forced into this error model.

All work should be grounded in the fundamental premise that a success value and an error value cannot coexist simultaneously.
C++ expresses this mutual exclusivity with std::variant, TypeScript with a discriminated union, Python with Success | Failure, and C# with Result<T>.SuccessCase | FailureCase.

Versions and Validation Environments

Implementation	Requirements the code targets	Environments verified in this document
C++	C++20, using `std::variant` and `std::optional`	MSYS2 UCRT64 g++ 16.1.0, syntax-checked with `-std=c++20 -Wall -Wextra -Werror -pedantic`
Python	Python 3.7 or later, using `from __future__ import annotations`, `dataclasses`, and `typing`	Tested on Python 3.14.6
C#	C# 10 or later, using `record struct`	`net8.0` target, running on .NET SDK 10.0.302 Release
TypeScript	TypeScript with support for private fields and discriminated unions; Node.js 18 or later is required to run `node:test`	TypeScript 7.0.2, running on Node.js 24.18.0

Implementation: C++
Requirements the code targets: C++20, using std::variant and std::optional
Environments verified in this document: MSYS2 UCRT64 g++ 16.1.0, syntax-checked with -std=c++20 -Wall -Wextra -Werror -pedantic

Implementation: Python
Requirements the code targets: Python 3.7 or later, using from __future__ import annotations, dataclasses, and typing
Environments verified in this document: Tested on Python 3.14.6

Implementation: C#
Requirements the code targets: C# 10 or later, using record struct
Environments verified in this document: net8.0 target, running on .NET SDK 10.0.302 Release

Implementation: TypeScript
Requirements the code targets: TypeScript with support for private fields and discriminated unions; Node.js 18 or later is required to run node:test
Environments verified in this document: TypeScript 7.0.2, running on Node.js 24.18.0

C++20 has no standard expected, so a small Result<T> is defined inline in this document.
If your project targets C++23, you can migrate the same contract to std::expected<T, DisjointSetError>.

C++20

C++

#include <cstddef>
#include <cstdint>
#include <numeric>
#include <optional>
#include <utility>
#include <variant>
#include <vector>

enum class DisjointSetErrorCode
{
    invalidElementCount,
    invalidNode,
};

struct DisjointSetError
{
    DisjointSetErrorCode code;
    std::size_t value;
};

template <typename T>
class [[nodiscard]] Result final
{
public:
    [[nodiscard]]
    static Result success(T value)
    {
        return Result(std::move(value));
    }

    [[nodiscard]]
    static Result failure(DisjointSetError error)
    {
        return Result(error);
    }

    [[nodiscard]]
    bool isSuccess() const noexcept
    {
        return std::holds_alternative<T>(storage_);
    }

    [[nodiscard]]
    const T& value() const&
    {
        return std::get<T>(storage_);
    }

    [[nodiscard]]
    T&& takeValue() &&
    {
        return std::get<T>(std::move(storage_));
    }

    [[nodiscard]]
    const DisjointSetError& error() const&
    {
        return std::get<DisjointSetError>(storage_);
    }

private:
    explicit Result(T value)
        : storage_(std::move(value))
    {
    }

    explicit Result(DisjointSetError error)
        : storage_(error)
    {
    }

    std::variant<T, DisjointSetError> storage_;
};

class DisjointSet final
{
public:
    [[nodiscard]]
    static Result<DisjointSet> create(
        std::size_t elementCount)
    {
        if (const auto error = elementCountError(elementCount);
            error.has_value())
        {
            return Result<DisjointSet>::failure(*error);
        }
        return Result<DisjointSet>::success(
            DisjointSet(elementCount));
    }

    [[nodiscard]]
    Result<bool> connect(
        std::uint32_t left,
        std::uint32_t right)
    {
        if (const auto error = validateNode(left);
            error.has_value())
        {
            return Result<bool>::failure(*error);
        }
        if (const auto error = validateNode(right);
            error.has_value())
        {
            return Result<bool>::failure(*error);
        }
        std::uint32_t leftRoot = findRoot(left);
        std::uint32_t rightRoot = findRoot(right);
        if (leftRoot == rightRoot)
        {
            return Result<bool>::success(false);
        }
        attachSmallerRoot(leftRoot, rightRoot);
        componentCount_ -= 1;
        return Result<bool>::success(true);
    }

    [[nodiscard]]
    Result<bool> areConnected(
        std::uint32_t left,
        std::uint32_t right)
    {
        if (const auto error = validateNode(left);
            error.has_value())
        {
            return Result<bool>::failure(*error);
        }
        if (const auto error = validateNode(right);
            error.has_value())
        {
            return Result<bool>::failure(*error);
        }
        return Result<bool>::success(
            findRoot(left) == findRoot(right));
    }

    [[nodiscard]]
    Result<std::uint32_t> getComponentSize(
        std::uint32_t node)
    {
        if (const auto error = validateNode(node);
            error.has_value())
        {
            return Result<std::uint32_t>::failure(*error);
        }
        return Result<std::uint32_t>::success(
            componentSize_[findRoot(node)]);
    }

    [[nodiscard]]
    std::size_t getComponentCount() const noexcept
    {
        return componentCount_;
    }

    [[nodiscard]]
    std::size_t getElementCount() const noexcept
    {
        return parent_.size();
    }

private:
    static constexpr std::size_t maximumElementCount =
        10'000'000;

    explicit DisjointSet(std::size_t elementCount)
        : parent_(elementCount),
          componentSize_(elementCount, 1),
          componentCount_(elementCount)
    {
        std::iota(
            parent_.begin(),
            parent_.end(),
            std::uint32_t{0});
    }

    std::vector<std::uint32_t> parent_;
    std::vector<std::uint32_t> componentSize_;
    std::size_t componentCount_;

    [[nodiscard]]
    std::uint32_t findRoot(std::uint32_t node)
    {
        while (parent_[node] != node)
        {
            parent_[node] = parent_[parent_[node]];
            node = parent_[node];
        }
        return node;
    }

    void attachSmallerRoot(
        std::uint32_t leftRoot,
        std::uint32_t rightRoot)
    {
        if (componentSize_[leftRoot]
            < componentSize_[rightRoot])
        {
            std::swap(leftRoot, rightRoot);
        }
        parent_[rightRoot] = leftRoot;
        componentSize_[leftRoot] +=
            componentSize_[rightRoot];
    }

    [[nodiscard]]
    std::optional<DisjointSetError> validateNode(
        std::uint32_t node) const
    {
        if (node >= parent_.size())
        {
            return DisjointSetError{
                DisjointSetErrorCode::invalidNode,
                node,
            };
        }
        return std::nullopt;
    }

    [[nodiscard]]
    static std::optional<DisjointSetError>
    elementCountError(std::size_t elementCount)
    {
        if (elementCount == 0
            || elementCount > maximumElementCount)
        {
            return DisjointSetError{
                DisjointSetErrorCode::invalidElementCount,
                elementCount,
            };
        }
        return std::nullopt;
    }
};

Usage:

C++

auto topologyResult = DisjointSet::create(6);
if (!topologyResult.isSuccess())
{
    return handle(topologyResult.error());
}
DisjointSet topology =
    std::move(topologyResult).takeValue();

for (const auto pair : {
         std::pair{0U, 1U},
         std::pair{1U, 2U},
         std::pair{3U, 4U},
         std::pair{2U, 4U},
     })
{
    const auto merged = topology.connect(
        pair.first,
        pair.second);
    if (!merged.isSuccess())
    {
        return handle(merged.error());
    }
}

const auto connected = topology.areConnected(0, 4);
const auto groupSize = topology.getComponentSize(3);

areConnected() and getComponentSize() both go through findRoot() internally, so they are logically queries but physically mutate the array.
This is why they are not const methods.

Validation failures are returned as error values in Result. false still represents the normal result of "already in the same component" and does not mix with errors. nodiscard forces the call site to check both success and failure.

Constructor initialization order

Placing validation in the constructor body means the two vector allocations have already been attempted by that point. componentCount_ is a single size_t value, so it requires no separate dynamic allocation.

C++

explicit DisjointSet(std::size_t elementCount)
    : parent_(elementCount),
      componentSize_(elementCount, 1),
      componentCount_(elementCount)
{
    validateElementCount(elementCount); // Too late.
}

If elementCount is 2 billion, the allocation is attempted before the error value can even be constructed. The create() in this document checks elementCountError() first and only calls the private constructor with a validated value.

Members are initialized in the order they are declared in the class body, not the order they appear in the initializer list. The current code uses the validated elementCount directly in every initializer expression, so it does not depend on this ordering. Still, there is a reason to understand this rule before changing member order.

Keep in mind that the reason the code above can read parent_ in componentSize_(parent_.size(), 1) is not because it appears first in the initializer expression, but because its declaration comes first in the class.

C++

std::vector<std::uint32_t> parent_;
std::vector<std::uint32_t> componentSize_;
std::size_t componentCount_;

When the order of the initializer list differs from the member declaration order, GCC and Clang normally warn with -Wreorder.³ When -Werror is also used, as in the validation options for this document, that warning becomes a build error. However, there is no guarantee that references to not-yet-constructed members in initializer expressions will always be diagnosed. It is therefore safer to use the validated elementCount directly rather than parent_.size().

GCC and Clang typically emit a -Wreorder warning, and if you use -Werror alongside it as in the validation options for this document, that warning becomes a build error. If you would rather not rely on declaration order, it is better to use elementCount directly in the initializer expression, or to introduce a delegating constructor that receives already-validated values.

Python

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, Optional, TypeVar, Union


T = TypeVar("T")


@dataclass(frozen=True)
class DisjointSetError:
    code: str
    value: object


@dataclass(frozen=True)
class Success(Generic[T]):
    value: T


@dataclass(frozen=True)
class Failure:
    error: DisjointSetError


Result = Union[Success[T], Failure]


class DisjointSet:
    _MAXIMUM_ELEMENT_COUNT = 10_000_000

    @classmethod
    def create(
        cls,
        element_count: object,
    ) -> Result[DisjointSet]:
        error = _element_count_error(
            element_count,
            cls._MAXIMUM_ELEMENT_COUNT,
        )
        if error is not None:
            return Failure(error)
        return Success(cls(int(element_count)))

    def __init__(self, element_count: int) -> None:
        self._parent = list(range(element_count))
        self._component_size = [1] * element_count
        self._component_count = element_count

    def connect(
        self,
        left: object,
        right: object,
    ) -> Result[bool]:
        left_error = self._node_error(left)
        if left_error is not None:
            return Failure(left_error)
        right_error = self._node_error(right)
        if right_error is not None:
            return Failure(right_error)
        left_root = self._find_root(int(left))
        right_root = self._find_root(int(right))
        if left_root == right_root:
            return Success(False)
        self._attach_smaller_root(left_root, right_root)
        self._component_count -= 1
        return Success(True)

    def are_connected(
        self,
        left: object,
        right: object,
    ) -> Result[bool]:
        left_error = self._node_error(left)
        if left_error is not None:
            return Failure(left_error)
        right_error = self._node_error(right)
        if right_error is not None:
            return Failure(right_error)
        return Success(
            self._find_root(int(left))
            == self._find_root(int(right))
        )

    def get_component_size(
        self,
        node: object,
    ) -> Result[int]:
        error = self._node_error(node)
        if error is not None:
            return Failure(error)
        root = self._find_root(int(node))
        return Success(self._component_size[root])

    def get_component_count(self) -> int:
        return self._component_count

    def get_element_count(self) -> int:
        return len(self._parent)

    def _find_root(self, node: int) -> int:
        while self._parent[node] != node:
            self._parent[node] = self._parent[
                self._parent[node]
            ]
            node = self._parent[node]
        return node

    def _attach_smaller_root(
        self,
        left_root: int,
        right_root: int,
    ) -> None:
        if (
            self._component_size[left_root]
            < self._component_size[right_root]
        ):
            left_root, right_root = right_root, left_root
        self._parent[right_root] = left_root
        self._component_size[left_root] += (
            self._component_size[right_root]
        )

    def _node_error(
        self,
        node: object,
    ) -> Optional[DisjointSetError]:
        if not _is_integer(node):
            return DisjointSetError("invalid_node", node)
        integer_node = int(node)
        if (
            integer_node < 0
            or integer_node >= len(self._parent)
        ):
            return DisjointSetError("invalid_node", node)
        return None


def _element_count_error(
    element_count: object,
    maximum_element_count: int,
) -> Optional[DisjointSetError]:
    if not _is_integer(element_count):
        return DisjointSetError(
            "invalid_element_count",
            element_count,
        )
    if (
        int(element_count) < 1
        or int(element_count) > maximum_element_count
    ):
        return DisjointSetError(
            "invalid_element_count",
            element_count,
        )
    return None


def _is_integer(value: object) -> bool:
    return isinstance(value, int) and not isinstance(value, bool)

Usage:

Python

created = DisjointSet.create(6)
if isinstance(created, Failure):
    handle(created.error)
else:
    topology = created.value

    for left, right in [(0, 1), (1, 2), (3, 4), (2, 4)]:
        merged = topology.connect(left, right)
        if isinstance(merged, Failure):
            handle(merged.error)

    connected = topology.are_connected(0, 4)
    group_size = topology.get_component_size(3)

An iterative loop is used instead of a recursive find(), because this avoids depending on Python's call stack limit even when the tree grows deeper than expected. However, recovering from or detecting invariant violations such as cycles in the parent array is a separate responsibility.

_is_integer() explicitly rejects bool because in Python, bool is a subtype of int. Since isinstance(True, int) is True, omitting this check would allow DisjointSet.create(True) to silently create a single-element set, and connect(True, False) would quietly pass through as connect(1, 0).
This implementation returns both inputs as Failure.

C#

using System;

public enum DisjointSetErrorCode
{
    InvalidElementCount,
    InvalidNode,
}

public readonly record struct DisjointSetError(
    DisjointSetErrorCode Code,
    int Value);

public abstract class Result<T>
{
    private Result()
    {
    }

    public sealed class SuccessCase : Result<T>
    {
        public SuccessCase(T value)
        {
            this.Value = value;
        }

        public T Value { get; }
    }

    public sealed class FailureCase : Result<T>
    {
        public FailureCase(DisjointSetError error)
        {
            this.Error = error;
        }

        public DisjointSetError Error { get; }
    }

    public static Result<T> Success(T value)
    {
        return new SuccessCase(value);
    }

    public static Result<T> Failure(
        DisjointSetError error)
    {
        return new FailureCase(error);
    }
}

public sealed class DisjointSet
{
    private const int MaximumElementCount =
        10_000_000;

    private readonly int[] parent;
    private readonly int[] componentSize;
    private int componentCount;

    private DisjointSet(int elementCount)
    {
        this.parent = new int[elementCount];
        this.componentSize = new int[elementCount];
        this.componentCount = elementCount;
        this.InitializeElements();
    }

    public static Result<DisjointSet> Create(
        int elementCount)
    {
        if (elementCount is < 1
            or > MaximumElementCount)
        {
            return Result<DisjointSet>.Failure(
                new DisjointSetError(
                    DisjointSetErrorCode.InvalidElementCount,
                    elementCount));
        }
        return Result<DisjointSet>.Success(
            new DisjointSet(elementCount));
    }

    public Result<bool> Connect(
        int left,
        int right)
    {
        if (this.GetNodeError(left) is { } leftError)
        {
            return Result<bool>.Failure(leftError);
        }
        if (this.GetNodeError(right) is { } rightError)
        {
            return Result<bool>.Failure(rightError);
        }
        int leftRoot = this.FindRoot(left);
        int rightRoot = this.FindRoot(right);
        if (leftRoot == rightRoot)
        {
            return Result<bool>.Success(false);
        }
        this.AttachSmallerRoot(leftRoot, rightRoot);
        this.componentCount -= 1;
        return Result<bool>.Success(true);
    }

    public Result<bool> AreConnected(
        int left,
        int right)
    {
        if (this.GetNodeError(left) is { } leftError)
        {
            return Result<bool>.Failure(leftError);
        }
        if (this.GetNodeError(right) is { } rightError)
        {
            return Result<bool>.Failure(rightError);
        }
        return Result<bool>.Success(
            this.FindRoot(left) == this.FindRoot(right));
    }

    public Result<int> GetComponentSize(int node)
    {
        if (this.GetNodeError(node) is { } error)
        {
            return Result<int>.Failure(error);
        }
        return Result<int>.Success(
            this.componentSize[this.FindRoot(node)]);
    }

    public int GetComponentCount()
    {
        return this.componentCount;
    }

    public int GetElementCount()
    {
        return this.parent.Length;
    }

    private int FindRoot(int node)
    {
        while (this.parent[node] != node)
        {
            this.parent[node] =
                this.parent[this.parent[node]];
            node = this.parent[node];
        }
        return node;
    }

    private void AttachSmallerRoot(
        int leftRoot,
        int rightRoot)
    {
        if (this.componentSize[leftRoot]
            < this.componentSize[rightRoot])
        {
            (leftRoot, rightRoot) =
                (rightRoot, leftRoot);
        }
        this.parent[rightRoot] = leftRoot;
        this.componentSize[leftRoot] +=
            this.componentSize[rightRoot];
    }

    private void InitializeElements()
    {
        for (
            int index = 0;
            index < this.parent.Length;
            index += 1)
        {
            this.parent[index] = index;
            this.componentSize[index] = 1;
        }
    }

    private DisjointSetError? GetNodeError(int node)
    {
        if (node < 0 || node >= this.parent.Length)
        {
            return new DisjointSetError(
                DisjointSetErrorCode.InvalidNode,
                node);
        }
        return null;
    }
}

Usage:

Result<DisjointSet> created = DisjointSet.Create(6);
if (created is Result<DisjointSet>.FailureCase failed)
{
    return Handle(failed.Error);
}
DisjointSet topology =
    ((Result<DisjointSet>.SuccessCase)created).Value;

foreach ((int left, int right) in new[]
{
    (0, 1),
    (1, 2),
    (3, 4),
    (2, 4),
})
{
    Result<bool> merged = topology.Connect(left, right);
    if (merged is Result<bool>.FailureCase failedMerge)
    {
        return Handle(failedMerge.Error);
    }
}

Result<bool> connected =
    topology.AreConnected(0, 4);
Result<int> groupSize =
    topology.GetComponentSize(3);

componentSize is meaningful only at root positions.
Encapsulate the array so external code cannot read it directly; it must always be accessed through FindRoot().

In C#, Create() validates the element count before allocating the arrays, and the private constructor accepts only validated values, so predictable input errors are not thrown as exceptions.

The design that returns explicit failures from the public API and the design that avoids allocations in internal loops should remain separate concerns. (This is a basic principle of API design, yet it is still hard to uphold in practice.)
At the public boundary, the current variant representation is retained, because its form cannot hold success and failure simultaneously, making it difficult for callers to produce an invalid state.

Currently, one call to Connect() produces one reference-type result, whereas FindRoot() and AttachSmallerRoot() create no result objects. Therefore, simply splitting out a ConnectUnchecked() does not reduce the allocation count as long as the public Connect() still returns Result<bool>.

If an internal batch operation that processes already-validated indices arises, add ConnectUnchecked() at that point. Only when such a batch calls the helper directly does a path exist that avoids creating a Result.

If profiling confirms that result-object allocations from the public API are an actual bottleneck, the options are to introduce an internal batch path or to redesign the API with a Merged, AlreadyConnected, InvalidInput enum and an out DisjointSetError contract. The latter can reduce allocations but is a design change that abandons the uniform error-propagation style of a general-purpose Result<T>. A value-type Result<T> is not a silver bullet either: default(Result<T>) can allow invalid combinations of tag, value, and error.

This is the frustrating part of programming. You write just a handful of small things, yet you have to document one by one what you were thinking and how another developer might read it. That part is genuinely irritating.

TypeScript

export type DisjointSetError = Readonly<{
  code: "invalid-element-count" | "invalid-node";
  value: number;
}>;

export type Result<T, E = DisjointSetError> =
  | Readonly<{ ok: true; value: T }>
  | Readonly<{ ok: false; error: E }>;

export function success<T, E = never>(
  value: T,
): Result<T, E>
{
  return { ok: true, value };
}

export function failure<T = never, E = never>(
  error: E,
): Result<T, E>
{
  return { ok: false, error };
}

export class DisjointSet
{
  static readonly #maximumElementCount =
    10_000_000;

  readonly #parent: Int32Array;
  readonly #componentSize: Int32Array;
  #componentCount: number;

  public static create(
    elementCount: number,
  ): Result<DisjointSet>
  {
    const error = validateElementCount(
      elementCount,
      DisjointSet.#maximumElementCount,
    );
    if (error !== undefined) {
      return failure(error);
    }
    return success(new DisjointSet(elementCount));
  }

  private constructor(elementCount: number)
  {
    this.#parent = new Int32Array(elementCount);
    this.#componentSize =
      new Int32Array(elementCount);
    this.#componentCount = elementCount;
    this.#initializeElements();
  }

  public connect(
    left: number,
    right: number,
  ): Result<boolean>
  {
    const leftError = this.#nodeError(left);
    if (leftError !== undefined) {
      return failure(leftError);
    }
    const rightError = this.#nodeError(right);
    if (rightError !== undefined) {
      return failure(rightError);
    }
    const leftRoot = this.#findRoot(left);
    const rightRoot = this.#findRoot(right);
    if (leftRoot === rightRoot) {
      return success(false);
    }
    this.#attachSmallerRoot(leftRoot, rightRoot);
    this.#componentCount -= 1;
    return success(true);
  }

  public areConnected(
    left: number,
    right: number,
  ): Result<boolean>
  {
    const leftError = this.#nodeError(left);
    if (leftError !== undefined) {
      return failure(leftError);
    }
    const rightError = this.#nodeError(right);
    if (rightError !== undefined) {
      return failure(rightError);
    }
    return success(
      this.#findRoot(left)
        === this.#findRoot(right),
    );
  }

  public getComponentSize(
    node: number,
  ): Result<number>
  {
    const error = this.#nodeError(node);
    if (error !== undefined) {
      return failure(error);
    }
    return success(
      this.#componentSize[this.#findRoot(node)],
    );
  }

  public getComponentCount(): number
  {
    return this.#componentCount;
  }

  public getElementCount(): number
  {
    return this.#parent.length;
  }

  #findRoot(node: number): number
  {
    while (this.#parent[node] !== node) {
      this.#parent[node] =
        this.#parent[this.#parent[node]];
      node = this.#parent[node];
    }
    return node;
  }

  #attachSmallerRoot(
    leftRoot: number,
    rightRoot: number,
  ): void
  {
    if (this.#componentSize[leftRoot]
      < this.#componentSize[rightRoot]) {
      [leftRoot, rightRoot] = [rightRoot, leftRoot];
    }
    this.#parent[rightRoot] = leftRoot;
    this.#componentSize[leftRoot] +=
      this.#componentSize[rightRoot];
  }

  #initializeElements(): void
  {
    for (
      let index = 0;
      index < this.#parent.length;
      index += 1
    ) {
      this.#parent[index] = index;
      this.#componentSize[index] = 1;
    }
  }

  #nodeError(
    node: number,
  ): DisjointSetError | undefined
  {
    if (!Number.isSafeInteger(node)
      || node < 0
      || node >= this.#parent.length) {
      return {
        code: "invalid-node",
        value: node,
      };
    }
    return undefined;
  }
}

export function validateElementCount(
  elementCount: number,
  maximumElementCount: number,
): DisjointSetError | undefined
{
  if (!Number.isSafeInteger(elementCount)
    || elementCount < 1
    || elementCount > maximumElementCount) {
    return {
      code: "invalid-element-count",
      value: elementCount,
    };
  }
  return undefined;
}

Int32Array is used instead of a plain number[] to fix the storage format and element width explicitly. At this upper bound, component sizes and parent indices are assumed not to exceed the signed 32-bit range.

This code was written against --strict and --noUnusedLocals.

Enabling --noUncheckedIndexedAccess causes typed array indexing to be treated as number | undefined as well. In projects using that setting, you need to narrow the value after #nodeError() into a local variable. The compiler does not automatically propagate the fact that a bounds check was performed through to subsequent array accesses.

Two trees of equal size

Because the comparison in attachSmallerRoot() uses <, when two components have the same size no swap occurs and right is placed under left. When sizes are equal, either side can serve as the root without changing the height upper bound of the resulting tree, so this tie-breaking rule can be chosen arbitrarily. Changing it to <= leaves both correctness and amortized complexity intact.

However, which side ends up as the root does change, so if a test asserts a specific root value, that is a signal the test is validating the wrong thing.

3. Call Site

External server IDs are strings, so a separate index layer converts them to dense integers. Union-Find itself knows nothing about strings, databases, or network I/O.

DisjointSet carries a contract that the element count is at least 1. An empty snapshot, however, is a normal result rather than an error, so the call site includes a branch that returns an empty index before calling DisjointSet.create(). Mixing this case into a DisjointSet | null field leaves null checks that can never be true on every lookup path. If the node map is empty, requireNode() returns an unknown-server-id error. Splitting the implementation in two removes that branch from the lookup path entirely.

TypeScript

import {
  DisjointSet,
  failure,
  success,
  type DisjointSetError,
  type Result,
} from "./ds.ts";

export type NetworkLink = Readonly<{
  leftServerId: string;
  rightServerId: string;
}>;

export type NetworkSnapshot = Readonly<{
  serverIds: readonly string[];
  links: AsyncIterable<NetworkLink>;
}>;

export type SnapshotReadError = Readonly<{
  code: "snapshot-read-failed";
  cause: unknown;
}>;

export type ConnectivityError =
  | DisjointSetError
  | SnapshotReadError
  | Readonly<{
    code: "invalid-server-id"
      | "duplicated-server-id"
      | "unknown-server-id";
    serverId: string;
  }>
  | Readonly<{
    code: "aborted";
  }>
  | Readonly<{
    code: "link-stream-failed";
    cause: unknown;
  }>;

type ConnectivityResult<T> =
  Result<T, ConnectivityError>;

export type NetworkSource = Readonly<{
  readSnapshotAsync: (
    signal?: AbortSignal,
  ) => Promise<Result<NetworkSnapshot, SnapshotReadError>>;
}>;

export interface ConnectivityIndex
{
  areConnected(
    leftServerId: string,
    rightServerId: string,
  ): ConnectivityResult<boolean>;
  getComponentSize(
    serverId: string,
  ): ConnectivityResult<number>;
  getComponentCount(): number;
}

export class EmptyConnectivityIndex
  implements ConnectivityIndex
{
  public areConnected(
    leftServerId: string,
    rightServerId: string,
  ): ConnectivityResult<boolean>
  {
    const leftError = serverIdError(leftServerId);
    if (leftError !== undefined) {
      return failure(leftError);
    }
    const rightError = serverIdError(rightServerId);
    if (rightError !== undefined) {
      return failure(rightError);
    }
    return failure({
      code: "unknown-server-id",
      serverId: leftServerId,
    });
  }

  public getComponentSize(
    serverId: string,
  ): ConnectivityResult<number>
  {
    const error = serverIdError(serverId);
    if (error !== undefined) {
      return failure(error);
    }
    return failure({
      code: "unknown-server-id",
      serverId,
    });
  }

  public getComponentCount(): number
  {
    return 0;
  }
}

export class ServerConnectivityIndex
  implements ConnectivityIndex
{
  readonly #nodeByServerId:
    ReadonlyMap<string, number>;
  readonly #sets: DisjointSet;

  public constructor(
    nodeByServerId: ReadonlyMap<string, number>,
    sets: DisjointSet,
  )
  {
    this.#nodeByServerId = nodeByServerId;
    this.#sets = sets;
  }

  public areConnected(
    leftServerId: string,
    rightServerId: string,
  ): ConnectivityResult<boolean>
  {
    const left = this.#getNode(leftServerId);
    if (!left.ok) {
      return left;
    }
    const right = this.#getNode(rightServerId);
    if (!right.ok) {
      return right;
    }
    return this.#sets.areConnected(left.value, right.value);
  }

  public getComponentSize(
    serverId: string,
  ): ConnectivityResult<number>
  {
    const node = this.#getNode(serverId);
    if (!node.ok) {
      return node;
    }
    return this.#sets.getComponentSize(node.value);
  }

  public getComponentCount(): number
  {
    return this.#sets.getComponentCount();
  }

  #getNode(
    serverId: string,
  ): ConnectivityResult<number>
  {
    return requireNode(
      this.#nodeByServerId,
      serverId,
    );
  }
}

export async function buildConnectivityIndexAsync(
  source: NetworkSource,
  signal?: AbortSignal,
): Promise<ConnectivityResult<ConnectivityIndex>>
{
  if (signal?.aborted) {
    return failure({ code: "aborted" });
  }
  let snapshotResult:
    Result<NetworkSnapshot, SnapshotReadError>;
  try {
    snapshotResult = await source.readSnapshotAsync(signal);
  } catch (cause) {
    if (signal?.aborted) {
    return failure({ code: "aborted" });
  }
    return failure({
      code: "snapshot-read-failed",
      cause,
    });
  }
  if (signal?.aborted) {
    return failure({ code: "aborted" });
  }
  if (!snapshotResult.ok) {
    return failure(snapshotResult.error);
  }

  const nodeIndex = createNodeIndex(
    snapshotResult.value.serverIds,
  );
  if (!nodeIndex.ok) {
    return nodeIndex;
  }
  if (nodeIndex.value.size === 0) {
    return success(new EmptyConnectivityIndex());
  }
  const setsResult = DisjointSet.create(
    nodeIndex.value.size,
  );
  if (!setsResult.ok) {
    return setsResult;
  }

  try {
    for await (const link of snapshotResult.value.links) {
      if (signal?.aborted) {
        return failure({ code: "aborted" });
      }
      const connected = connectLink(
        setsResult.value,
        nodeIndex.value,
        link,
      );
      if (!connected.ok) {
        return connected;
      }
    }
  } catch (cause) {
   if (signal?.aborted) {
    return failure({ code: "aborted" });
  }
    return failure({
      code: "link-stream-failed",
      cause,
    });
  }
  if (signal?.aborted) {
    return failure({ code: "aborted" });
  }
  return success(new ServerConnectivityIndex(
    nodeIndex.value,
    setsResult.value,
  ));
}

function createNodeIndex(
  serverIds: readonly string[],
): ConnectivityResult<ReadonlyMap<string, number>>
{
  const index =
    new Map<string, number>();
  for (const serverId of serverIds) {
    const error = serverIdError(serverId);
    if (error !== undefined) {
      return failure(error);
    }
    if (index.has(serverId)) {
      return failure({
        code: "duplicated-server-id",
        serverId,
      });
    }
    index.set(serverId, index.size);
  }
  return success(index);
}

function connectLink(
  sets: DisjointSet,
  nodes: ReadonlyMap<string, number>,
  link: NetworkLink,
): ConnectivityResult<void>
{
  const left =
    requireNode(nodes, link.leftServerId);
  if (!left.ok) {
    return left;
  }
  const right =
    requireNode(nodes, link.rightServerId);
  if (!right.ok) {
    return right;
  }
  const merged = sets.connect(left.value, right.value);
  if (!merged.ok) {
    return merged;
  }
  return success(undefined);
}

function requireNode(
  nodes: ReadonlyMap<string, number>,
  serverId: string,
): ConnectivityResult<number>
{
  const error = serverIdError(serverId);
  if (error !== undefined) {
    return failure(error);
  }
  const node = nodes.get(serverId);
  if (node === undefined) {
    return failure({
      code: "unknown-server-id",
      serverId,
    });
  }
  return success(node);
}

function serverIdError(
  serverId: string,
): ConnectivityError | undefined
{
  if (!/^[A-Za-z0-9_.:-]{1,100}$/.test(
    serverId,
  )) {
    return {
      code: "invalid-server-id",
      serverId,
    };
  }
  return undefined;
}

On separation of responsibilities:

Text

NetworkSource
= Server and link snapshot I/O

Node Index
= External string ID
→ Compact integer index conversion

DisjointSet
= Manages connected components of integer elements

ConnectivityIndex
= Business ID-based query API

Snapshot Builder
= Load → Validate → Map → Union

Rebuild Policy
= Handles link deletion or snapshot version changes

The root index of Union-Find is not exposed in the external API. The root can change with subsequent union operations and should be considered an internal implementation detail.

Because connectLink() and #getNode() both use the same requireNode(), the error code for an unknown server ID is centralized in one place across both the loading and lookup sides. If buildConnectivityIndexAsync() returns only the Map and discards DisjointSet as a local variable, no connectivity information survives despite the name. The return value must hold DisjointSet within its lifetime.

Lifetime of the index

What actually dominates memory here is not the Union-Find arrays but the string map.
A measurement inserting 1 million 36-character IDs into a Map<string, number> on Node 22 produced approximately 119.5 MiB, though this is an observed value that varies with the Node version, the timing of ID creation, the baseline before or after a full GC, and runtime options.

When comparing, you must also separate the measurement axes.

Text

Map/string delta:
approximately 119.5 MiB by `heapUsed`

Two `Int32Array`s, 1,000,000 elements each:
approximately 7.6 MiB by `arrayBuffers`

heapUsed primarily reflects the V8 heap, while arrayBuffers reflects the typed array backing store. Comparing the two as absolute values on the same axis is misleading, so
to produce reproducible numbers you should record the Node version, runtime options, ID creation timing, baseline, and the process.memoryUsage() fields both before and after the measurement. (The differences between versions are larger than you might expect.)

If you cache a ConnectivityIndex for the entire lifetime of the process, this map stays alive along with it, so the lifetime policy should be determined at the call site, not in the data structure itself.

Text

Per-request index: release the reference after each response
Long-term cache: store a snapshot version together with a TTL
Rebuild: create a new index, then swap the reference
Read-heavy workloads: let the upper-level session hold a validated integer handle

WeakRef or FinalizationRegistry is not the right place to obscure that lifetime. Create the index explicitly and discard it explicitly.

4. Reading Order

Text

Are element IDs dense in the range 0..N-1?
→ Is `parent[i]` a valid index?
→ Is the initial `parent[i]` equal to `i`?
→ Does `find` traverse up to the root?
→ Does `find` compress the path during traversal?
→ Does `union` find both roots before merging?
→ If both roots are already the same, does it leave the state unchanged?
→ Is the smaller component attached to the larger component?
→ Is `size` updated only at the new root?
→ Is `componentCount` decremented only on an actual merge?
→ Does size validation happen before array allocation?
→ Is the root never exposed as an external persistent ID?

Key code review points:

Text

parent[right] = left

it should be the following, not the former.

Text

parent[rootOfSmallerComponent]
= rootOfLargerComponent

You must union the representative roots, not the elements themselves.

5. Misconceptions That Arise in Practice

Union-Find cannot handle edge deletion

If you delete edge 1—2 from the following graph, the component may split into two.

Text

0 — 1 — 2 — 3

However, Union-Find holds no information about which edge connected two sets, so you are left with the following options.

Text

Options for handling deletions:
- Full rebuild from snapshot
- Offline processing with reversed time order
- Rollback DSU
- Fully dynamic connectivity data structure

First, verify whether your workload involves edge additions only. A fully dynamic connectivity data structure that handles arbitrary deletions in poly-logarithmic time is a separate algorithm from Union-Find.⁴

It does not provide the actual connection path

Text

areConnected(0, 7)
→ true

Union-Find does not return an actual graph path such as 0→3→5→7. If you need the path, you must maintain a separate adjacency graph and run BFS, DFS, or a similar traversal. The parent forest is not the same as the edges of the original graph (This is an explanation from GPT. I'm still a bit confused about this part, so I'm noting that I used GPT. I still find it a bit hard to understand why this code doesn't return the graph path.).

Root is not a stable component ID

Suppose the current state is as follows.

Text

root({0, 1, 2}) = 0
root({3, 4, 5, 6}) = 3

When two sets are merged, union-by-size changes the root of the smaller set.

Text

union(0, 3)
root({0,1,2,3,4,5,6})
= 3

If you use the root as a DB key or a group ID exposed to users, that identifier changes on subsequent union operations. If a stable group ID is required for business purposes, establish a separate canonical ID policy.

`componentSize[node]` is not valid for non-root elements

After merging, the size value of the smaller root is intentionally left as-is rather than being reset to 0.

Text

parent[2] = 0
`componentSize[2]` = previous value

Valid lookup:

Text

componentSize[find(2)]

Invalid lookup:

Text

componentSize[2]

This is also the reason why the internal arrays are not exposed externally.

`find()` looks like a read, but it performs a write

Path compression modifies the parent pointers.

Text

Before compression:
7 → 5 → 3 → 0

find(7)

After compression (example):
7 → 3 → 0

areConnected() and getComponentSize() look like pure queries by name, but both go through findRoot() and therefore mutate the underlying arrays. This matters because even if multiple threads only call these two methods, sharing them without synchronization causes a data race. Efficient concurrent Union-Find is more complex than simply attaching a single lock to the arrays; separate CAS-based algorithms and analyses exist for this purpose.⁵

Operational policy for usage:

Text

Build phase:
A single owner performs union and path halving

Publish phase:
Generate an immutable snapshot with all paths fully compressed

Read phase:
Use read-only root lookup

Alternatively, choose an actor, a lock, or partitioned ownership.

Rollback and path shortening do not mix well

This is important enough to highlight in red.

A rollback DSU records a change history on a stack and reverts to a previous state. Path shortening techniques, including path halving, modify multiple parent pointers in a single find() call, which significantly increases the number of entries that must be recorded for reversal.

If rollback is a core requirement, the general recommendation is:

Text

- maintain union-by-size
- omit path shortening, including path halving
- record only the changed parent and size onto the stack

Prioritize undo capability over amortized performance. The per-operation cost of this combination becomes O(log N), and that is a worst-case bound, not an amortized one.

Do not use external IDs directly as array indices

Sizing an array to fit the next ID wastes space.

Text

server IDs:
17
8,000,000
2,000,000,000

Even if there are only 3 actual elements, an array sized to the maximum ID is required.

Text

External ID
→ dense index mapping
→ 0, 1, 2

Array efficiency in Union-Find comes from having a dense index space.

A duplicate union can be a no-op rather than a failure

Text

connect(0, 1)
connect(0, 1)

The second call returns false because the two elements already belong to the same set.

Text

Meaning of false:
The input is invalid
No

Meaning of false:
No new component merge occurred

Whether the business layer treats a duplicate link as an error is a separate policy decision that must be checked explicitly.

Memory usage is O(N)

Two 32-bit arrays, one for parent and one for size, consume 8 bytes of raw storage per element.

Text

N = 10,000,000
raw arrays:
80,000,000 bytes
= 76.2939453125 MiB
≈ 76.3 MiB

A Python object list can carry significantly more overhead for the same logical structure (as confirmed by actual measurement). And as noted earlier, a string ID map can be an order of magnitude or more larger than this raw storage. For large-scale inputs, measure actual memory usage per language.

Notes on failures:

Text

Directly linking elements via parent pointers, creating a cycle
Not finding the root before performing a union
Storing the root as a permanent business ID
Directly reading the size slot of a non-root node
Treating edge deletion as the inverse operation of union
Using an external 64-bit ID directly as an array index
Assuming concurrent find operations are read-only
Using path compression (including path halving) in a rollback DSU
Decrementing `componentCount` on a duplicate union
Interpreting the parent forest as a graph path to obtain the actual route
Allocating the array before validating the size
No one owning the lifetime of the string index

6. Incorrect Examples

TypeScript

class DisjointSetBad
{
  readonly #parent: number[];

  public constructor(size: number)
  {
    this.#parent =
      Array.from(
        { length: size },
        (value, index) => index,
      );
  }

  public connect(
    left: number,
    right: number,
  ): void
  {
    this.#parent[right] = left;
  }

  public find(node: number): number
  {
    if (this.#parent[node] === node) {
      return node;
    }
    return this.find(
      this.#parent[node],
    );
  }
}

The following call sequence is examined below.

Text

connect(0, 1)
parent[1] = 0

connect(1, 2)
parent[2] = 1

connect(2, 0)
parent[0] = 2

Result:

Text

0 → 2 → 1 → 0

A cycle is created instead of a parent forest. find(0) never terminates (this was an example written when first learning the concept).

Specific issues:

Text

Does not find the roots of `left` and `right`.
Does not check whether the two sets are already connected.
No union-by-size or rank.
No path compression, including path halving.
Recursive calls consume stack space on long chains.
No index range validation.
Cannot track component sizes or counts.
Does not detect cycles even when they occur.

union is not a function that connects two arbitrary nodes.

Text

Incorrect meaning:
Set the parent of `right` to `left`

Correct meaning:
Merge the root of the set containing `right` with
the root of the set containing `left`

7. Using in Production

Union-Find looks correct on small examples, but off-by-one errors tend to hide in edge cases involving root reassignment and path halving. Property-based testing that compares BFS results on a reference graph against randomly generated operations is effective for catching these bugs. (This is a natural and expected conclusion from general experience.) Property-based testing that compares BFS results on a reference graph against randomly generated operations is effective.

TypeScript Deterministic Random Testing

TypeScript

import assert from "node:assert/strict";
import test from "node:test";
import {
  DisjointSet,
  type Result,
} from "./ds.ts";

test("Union-Find matches reference graph connectivity", () =>
{
  const nodeCount = 128;
  for (const seed of [0x5eed, 0x1, 0xdeadbeef]) {
    const created = DisjointSet.create(nodeCount);
    assert.ok(created.ok);
    if (!created.ok) {
      assert.fail(JSON.stringify(created.error));
    }
    const sets = created.value;
    const graph = createEmptyGraph(nodeCount);
    const touched = new Set<number>();
    const random = createDeterministicRandom(seed);
    for (
      let step = 0;
      step < 20_000;
      step += 1
    ) {
      const left = randomIndex(random, nodeCount);
      const right = randomIndex(random, nodeCount);
      touched.add(left);
      touched.add(right);
      const expectedMerged =
        !isConnectedByGraph(graph, left, right);
      const actualMerged = sets.connect(left, right);
      assert.ok(actualMerged.ok);
      if (!actualMerged.ok) {
        assert.fail(JSON.stringify(actualMerged.error));
      }
      addUndirectedEdge(graph, left, right);
      assert.equal(actualMerged.value, expectedMerged);
      verifyRandomQueries(
        sets,
        graph,
        random,
        nodeCount,
      );
    }
    assert.equal(touched.size, nodeCount);
  }
});

test("Component sizes are preserved across chain, star, and balanced merge orderings", () =>
{
  const scenarios: readonly {
    readonly name: string;
    readonly edges: readonly (
      readonly [number, number]
    )[];
  }[] = [
    {
      name: "chain",
      edges: [
        [0, 1], [1, 2], [2, 3], [3, 4],
        [4, 5], [5, 6], [6, 7],
      ],
    },
    {
      name: "star",
      edges: [
        [0, 1], [0, 2], [0, 3], [0, 4],
        [0, 5], [0, 6], [0, 7],
      ],
    },
    {
      name: "balanced",
      edges: [
        [0, 1], [2, 3], [4, 5], [6, 7],
        [0, 2], [4, 6], [0, 4],
      ],
    },
  ];

  for (const scenario of scenarios) {
    const created = DisjointSet.create(8);
    assert.ok(created.ok, scenario.name);
    if (!created.ok) {
      assert.fail(JSON.stringify(created.error));
    }
    const sets = created.value;
    for (const [left, right] of scenario.edges) {
      assert.equal(
        requireSuccess(sets.connect(left, right)),
        true,
        scenario.name,
      );
    }
    assert.equal(
      sets.getComponentCount(),
      1,
      scenario.name,
    );
    for (let node = 0; node < 8; node += 1) {
      assert.equal(
        requireSuccess(sets.getComponentSize(node)),
        8,
        scenario.name,
      );
    }
  }
});

test("Duplicate unions do not reduce the component count", () =>
{
  const created = DisjointSet.create(4);
  assert.ok(created.ok);
  if (!created.ok) {
    assert.fail(JSON.stringify(created.error));
  }
  const sets = created.value;
  const firstMerge = sets.connect(0, 1);
  assert.ok(firstMerge.ok);
  if (!firstMerge.ok) {
    assert.fail(JSON.stringify(firstMerge.error));
  }
  assert.equal(
    firstMerge.value,
    true,
  );
  assert.equal(
    sets.getComponentCount(),
    3,
  );
  const repeatedMerge = sets.connect(1, 0);
  assert.ok(repeatedMerge.ok);
  if (!repeatedMerge.ok) {
    assert.fail(JSON.stringify(repeatedMerge.error));
  }
  assert.equal(repeatedMerge.value, false);
  assert.equal(
    sets.getComponentCount(),
    3,
  );
});

test("Component size equals the actual number of elements", () =>
{
  const created = DisjointSet.create(6);
  assert.ok(created.ok);
  if (!created.ok) {
    assert.fail(JSON.stringify(created.error));
  }
  const sets = created.value;
  for (const [left, right] of [
    [0, 1],
    [1, 2],
    [3, 4],
    [2, 4],
  ]) {
    const merged = sets.connect(left, right);
    assert.ok(merged.ok);
  }
  for (const node of [0, 1, 2, 3, 4]) {
    const size = sets.getComponentSize(node);
    assert.ok(size.ok);
    if (!size.ok) {
      assert.fail(JSON.stringify(size.error));
    }
    assert.equal(size.value, 5);
  }
  const isolatedSize = sets.getComponentSize(5);
  assert.ok(isolatedSize.ok);
  if (!isolatedSize.ok) {
    assert.fail(JSON.stringify(isolatedSize.error));
  }
  assert.equal(isolatedSize.value, 1);
});

test("Out-of-range inputs produce a `Result` error", () =>
{
  const created = DisjointSet.create(4);
  assert.ok(created.ok);
  if (!created.ok) {
    assert.fail(JSON.stringify(created.error));
  }
  assert.deepEqual(
    created.value.areConnected(0, 4),
    { ok: false, error: {
      code: "invalid-node",
      value: 4,
    } },
  );
  assert.deepEqual(
    created.value.areConnected(-1, 0),
    { ok: false, error: {
      code: "invalid-node",
      value: -1,
    } },
  );
  assert.deepEqual(
    created.value.getComponentSize(1.5),
    { ok: false, error: {
      code: "invalid-node",
      value: 1.5,
    } },
  );
  assert.deepEqual(
    DisjointSet.create(0),
    { ok: false, error: {
      code: "invalid-element-count",
      value: 0,
    } },
  );
  assert.deepEqual(
    DisjointSet.create(10_000_001),
    { ok: false, error: {
      code: "invalid-element-count",
      value: 10_000_001,
    } },
  );
});

type ReferenceGraph =
  readonly Set<number>[];

function createEmptyGraph(
  nodeCount: number,
): ReferenceGraph
{
  return Array.from(
    { length: nodeCount },
    () => new Set<number>(),
  );
}

function requireAdjacency(
  graph: ReferenceGraph,
  node: number,
): Set<number>
{
  const adjacency = graph[node];
  if (adjacency === undefined) {
    assert.fail("reference graph node is out of range.");
  }
  return adjacency;
}

function addUndirectedEdge(
  graph: ReferenceGraph,
  left: number,
  right: number,
): void
{
  requireAdjacency(graph, left)
    .add(right);
  requireAdjacency(graph, right)
    .add(left);
}

function isConnectedByGraph(
  graph: ReferenceGraph,
  start: number,
  target: number,
): boolean
{
  if (start === target) {
    return true;
  }
  const visited =
    new Set<number>([start]);
  const queue = [start];
  for (
    let index = 0;
    index < queue.length;
    index += 1
  ) {
    const current = queue[index];
    assert.ok(current !== undefined);
    for (
      const next of requireAdjacency(
        graph,
        current,
      )
    ) {
      if (next === target) {
        return true;
      }
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
  }
  return false;
}

function verifyRandomQueries(
  sets: DisjointSet,
  graph: ReferenceGraph,
  random: () => number,
  nodeCount: number,
): void
{
  for (let query = 0; query < 8; query += 1) {
    const left =
      randomIndex(random, nodeCount);
    const right =
      randomIndex(random, nodeCount);
    assert.equal(
      requireSuccess(
        sets.areConnected(left, right),
      ),
      isConnectedByGraph(
        graph,
        left,
        right,
      ),
    );
  }
}

function requireSuccess<T>(
  result: Result<T>,
): T
{
  if (!result.ok) {
    assert.fail(JSON.stringify(result.error));
  }
  return result.value;
}

function randomIndex(
  random: () => number,
  nodeCount: number,
): number
{
  return Math.floor(
    (random() / 0x1_0000_0000) * nodeCount,
  );
}

function createDeterministicRandom(
  seed: number,
): () => number
{
  let state = seed >>> 0;
  return () =>
  {
    state = (
      Math.imul(state, 1_664_525)
      + 1_013_904_223
    ) >>> 0;
    return state;
  };
}

Actual Execution Results

Executed with LCG seeds 0x5eed, 0x1, and 0xdeadbeef, each using 128 nodes, 20,000 union operations, and 8 connectivity queries after every union.

Each seed produces 160,000 queries. The figures below are observations for seed 0x5eed.

Text

Actual merges: 127
Already connected (no-op): 19,873
Distinct nodes selected: 128
Final component count: 1
Component size of node 0: 128

Since 127 = 128 - 1, this matches the actual number of merges needed for all nodes to form a single component.
Every union and query result matched the BFS result from the reference graph. The C# Release build was also verified to produce the same values for the same input.

Text

PASS: C# Result contract, 127 merges, 19873 no-ops, 128/128 indices.

invalid-node was confirmed to be returned for negative values and nodes above the upper bound, and invalid-element-count for 0 and 10,000,001, in both C# and TypeScript. The Python implementation was also verified by execution to return Failure(...) for 0, True, and out-of-range nodes.

The ConnectivityIndex boundary cases were also exercised. Loading servers a, b, c with links a-b and b-c caused areConnected("a", "c") to return success(true). A snapshot containing a twice returned duplicated-server-id; a link referencing a-missing returned unknown-server-id; and an already-cancelled signal returned an aborted error. Cases where snapshot reading or the link stream threw a cancellation exception, or where the signal was cancelled just before reading completed, were also confirmed to convert to aborted.

Points that are problematic in testing.

Using random() % nodeCount to produce an index means only the low-order bits of this LCG are consumed. The harness above consumes exactly 18 random numbers per step.

That is two calls for left and right, plus 8 calls × 2 for verifyRandomQueries(). If you look only at the same argument position within each step, the 18-step stride means state % 128 visits only 64 residues. However, when all 18 positions within a step are considered together, all 128 nodes can be selected.

The more direct problem with using low-order bits as-is is the pair structure. Because both the multiplier and the increment of this LCG are odd, the lowest bit flips on every call; using two consecutive outputs as left and right always pairs values of opposite parity.
Same-parity pairs and self-pairs are never generated. It is best to say that randomIndex() avoids this low-bit cycle issue by scaling the high-order bits. When nodeCount is not a power of two, it is more accurate to describe the approach as eliminating the direct low-bit periodicity flaw rather than claiming a perfectly uniform distribution.

requireAdjacency() and assert.ok(current !== undefined) ensure this test file passes as-is even in projects where --noUncheckedIndexedAccess is enabled. Because the test fails immediately instead of substituting undefined for another node, any defect in the reference implementation is surfaced explicitly.

Programmers should always write things down explicitly so they won't be confused when they come back to the code later.

Core invariants:

Text

Initial state:
componentCount == N

Actual merge:
componentCount decreases by exactly 1

Duplicate merge:
componentCount does not change

All nodes:
areConnected(node, node) == true

All nodes in the same component:
getComponentSize(node) is identical

After all unions:
Equivalent to reference BFS connectivity

Empty snapshot:
getComponentCount() == 0 and lookups return Result error

Performance measurement criteria

Comparison targets:

Text

1. BFS/DFS per query
2. Union-Find without optimization
3. Union-by-size only
4. Union-by-size + path halving

Measurement variables:

Text

- Number of elements N
- Ratio of Union to Query operations
- Ratio of duplicate edges
- Input ordering
- Component size distribution
- External ID mapping cost
- Memory usage

Even if Union-Find itself is fast, the cost of hashing a string ID on every call can dominate. You need to measure across the entire call boundary together.

8. C++ / Python / C# / TypeScript Comparison Notes

Language	Parent storage	Size storage	Primary concern
C++	`vector<uint32_t>`	`vector<uint32_t>`	Data race between member declaration order and concurrent path shortening
Python	`list[int]`	`list[int]`	`bool` is a subtype of `int`; object overhead and interpreter loop
C#	`int[]`	`int[]`	`AreConnected()` and `GetComponentSize()` perform internal mutation
TypeScript	`Int32Array`	`Int32Array`	External string ID translation cost and index lifetime

Language: C++
Parent storage: vector<uint32_t>
Size storage: vector<uint32_t>
Primary concern: Data race between member declaration order and concurrent path shortening

Language: Python
Parent storage: list[int]
Size storage: list[int]
Primary concern: bool is a subtype of int; object overhead and interpreter loop

Language: C#
Parent storage: int[]
Size storage: int[]
Primary concern: AreConnected() and GetComponentSize() perform internal mutation

Language: TypeScript
Parent storage: Int32Array
Size storage: Int32Array
Primary concern: External string ID translation cost and index lifetime

C++

Two dense primitive vectors provide good locality and clear ownership. Because findRoot() modifies the parent array, synchronization is required even for shared reads.

Using uint32_t explicitly caps the maximum element count. Unconditionally using size_t can double the memory footprint of the parent array in a 64-bit environment, so choose the index width to match the actual maximum scale.

The fact that member initialization follows declaration order is a pitfall specific to this language. If you reorder member declarations while keeping the constructor from Chapter 2 as-is, it silently becomes undefined behavior.

Python

The algorithm is the same, but list[int] is not a packed 32-bit integer array. There is representation overhead for each list slot and integer object.

If millions of elements become a bottleneck, you can consider the following.

Text

- array("I")
- NumPy array
- Cython
- native extension

However, if the Python loop itself is on the hot path, changing only the storage representation may not be sufficient.

C#

Two int[] arrays are compact, and the GC does not track each element as a separate object. With 10 million elements, a single array occupies 40 MB and lands on the large object heap. For large arrays, you should consider managed heap policy and snapshot lifetime together.

AreConnected() and GetComponentSize() look like read operations by name, but they modify the array via path halving. Exposing this fact through API documentation or a separate read-only snapshot type is likely central to good API design.

TypeScript

Int32Array stores parent and size values with a fixed width. The intent is clearer than a plain number[], and it does not create sparse holes.

You could use Uint32Array here instead. Since node indices and component sizes are fundamentally non-negative, Uint32Array is a closer fit from a storage-representation standpoint. With an upper bound of 10 million, the roughly 2.1 billion range of Int32Array is more than sufficient, and since both arrays have the same element width, memory usage is identical.

That said, Uint32Array does not appear to prevent negative assignment at the type level in TypeScript (confirmed by testing).

The element type remains number, and values[0] = -1 is accepted, then stored as 4_294_967_295 after ToUint32 conversion. So it appears that boundary validation such as #nodeError() is still necessary even with an unsigned array. The choice between Int32Array and Uint32Array is ultimately a matter of storage representation and sentinel policy.

In production services, however, the following costs may dominate.

Text

serverId string
→ Map lookup
→ dense node index
→ Union-Find operation

If queries are frequent, callers can cache a validated NodeId handle within an upper-level session rather than passing a string on every call.

Common contract

Ultimately, these are the points that any implementation of this structure must address in common.

Text

Shared contract:
- Element ID range
- Initial component definition
- union-by-size rules
- Path shortening method (whether compression, splitting, or halving is used)
- Return semantics for duplicate union
- Root privacy policy
- Edge deletion policy
- Concurrency ownership
- Order of validation and allocation

9. Further considerations

If edge deletions occur only once a day, is a full rebuild simpler and faster than maintaining a dynamic connectivity structure?
Without exposing the root externally, how do you reliably attach per-component business metadata?
In parallel ingestion scenarios, which structure better fits the actual workload: a single concurrent DSU, or per-worker local DSUs merged afterward?
When rollback is required and path compression must be abandoned, what change history should be stored on the stack?
When external IDs are strings, does the Map lookup cost end up exceeding the cost of the Union-Find operations themselves?
If actual connection paths are also needed, are you willing to accept the memory overhead of maintaining both a Union-Find structure and an adjacency graph?
If measurements show the string index is larger than the data structure itself, who owns that index and when should it be discarded?
How do you translate Result error codes into responses for HTTP, CLI, and job-queue consumers?

10. Summary

Union-Find efficiently tracks the connected components of a graph as edges are added.
union must merge the roots of the two elements, not the elements themselves.
Union-by-size attaches the smaller tree to the larger one, and path halving reduces the traversal path on repeated lookups. This combination achieves an inverse Ackermann amortized bound.
The root and the root's size are internal implementation details, not stable business identifiers.
areConnected() and getComponentSize() are write operations despite their names.
Edge deletion, actual path retrieval, and concurrent modification fall outside the responsibility of a basic Union-Find.
Size validation must happen before array allocation, and in C++ that order depends on the member declaration order.
What actually dominates memory may not be the integer arrays but the external ID map.
Correctness can be verified by comparing BFS results on a reference graph against randomly generated operations.

Text

Do not link elements directly.
Find the root of each element,
and attach only the root of the smaller component
under the root of the larger component.

A personal note: the key insight is to design the fast algorithm and the object allocation model together rather than treating them separately. Even when you swap out the algorithm, if input validation, failure contracts, state ownership, and call boundaries are preserved, the outer structure largely remains and can be reused. What changes is the internal data structure and performance characteristics. In other words, failure contracts and state ownership are roughly what you might call a matter of the programmer's style.

1. Problem Setup

2. Core Representation

Error Handling

Versions and Validation Environments

C++20

Constructor initialization order

Python

C#

TypeScript

Two trees of equal size

3. Call Site

Lifetime of the index

4. Reading Order

5. Misconceptions That Arise in Practice

Union-Find cannot handle edge deletion

It does not provide the actual connection path

Root is not a stable component ID

componentSize[node] is not valid for non-root elements

find() looks like a read, but it performs a write

Rollback and path shortening do not mix well

Do not use external IDs directly as array indices

A duplicate union can be a no-op rather than a failure

Memory usage is O(N)

6. Incorrect Examples

7. Using in Production

TypeScript Deterministic Random Testing

Actual Execution Results

Points that are problematic in testing.

Performance measurement criteria

8. C++ / Python / C# / TypeScript Comparison Notes

C++

Python

C#

TypeScript

Common contract

9. Further considerations

10. Summary

Footnotes

`componentSize[node]` is not valid for non-root elements

`find()` looks like a read, but it performs a write