Incremental Connectivity Tracking with Union-Find

Union-Find, also called Disjoint Set Union, is a data structure that tracks which connected component each element belongs to. Every element starts out separate, union(a, b) merges two sets, and find(a) returns the representative root of the set the element belongs to.

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 win is that it never walks a whole graph object over and over — two densely packed integer arrays answer connectivity questions. That suits problems where connections are only ever added: network endpoints, image regions, account merge candidates, Kruskal's minimum spanning tree.

The trade-off is a narrow feature set: Union-Find tells you whether two elements are connected, but not the actual connection path.

It also cannot directly handle an edge deletion that splits a component. If you need deletions, rebuild from scratch, process offline with a rollback DSU, or use a dynamic connectivity 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

Suppose a network management system receives connection information between servers in order.

Text

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

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

At first, every server is its own component.

Text

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

Applying 0—1 and 1—2 gives this.

Text

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

Applying 3—4 as well gives this.

Text

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

Finally, applying 2—4 merges the two components into one.

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

The implementation assumes element IDs are dense integers in 0..N-1. UUIDs and string IDs are 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 from connect() is not an error — it is the normal result meaning the two nodes were already in the same component. invalid-node and invalid-element-count are different: explicit failures where the caller has to fix its input or reject the request. Memory exhaustion, defects in the runtime itself, and broken 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 come back as the error value of Result. false is still the normal "already in the same component" result and never mixes with errors. nodiscard forces the call site to check both success and failure.

Constructor initialization order

If validation sits in the constructor body, both vector allocations have already been attempted by then. componentCount_ is a single size_t value, so it needs no dynamic allocation of its own.

C++

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

With elementCount at 2 billion, the allocation is attempted before the error value can even be built. So create() checks elementCountError() first and calls the private constructor only 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 usually emit a -Wreorder warning, and with -Werror alongside it, as in the validation options here, that warning becomes a build error. If you don't want to rely on declaration order, use elementCount directly in the initializer, or add a delegating constructor that takes 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)

I used a loop instead of a recursive find() so that nothing depends on Python's call stack limit when the tree runs deeper than expected. Detecting or recovering from invariant violations such as a cycle 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() checks the element count before allocating the arrays, and the private constructor takes only validated values, so predictable input errors never turn into 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.

One Connect() call allocates one reference-type result, while FindRoot() and AttachSmallerRoot() allocate no result objects. So however finely you split off ConnectUnchecked(), the allocation count stays the same as long as public Connect() returns Result<bool>.

When an internal batch that runs already-validated indexes in bulk shows up, that is the time to add ConnectUnchecked() — a path without a Result exists only when that batch calls the helpers directly.

If profiling confirms that result-object allocation in the public API is a real bottleneck, there are two options: add an internal batch path, or change the API to a Merged, AlreadyConnected, InvalidInput enum with an out DisjointSetError contract. The latter lowers allocations but gives up the uniform error propagation of a general-purpose Result<T>. A value-type Result<T> is no silver bullet either — it can accept default(Result<T>) or a bad combination of tag, value, and error.

This is the irritating part of programming: you write a handful of small things, and you have to spell out one by one what you were thinking and how another developer will read it. Honestly, that is the most irritating part.

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 pins down the storage format and element width more firmly than a plain number[]. At this upper bound, neither component sizes nor parent indexes exceed the signed 32-bit range.

This was written with --strict and --noUnusedLocals enabled.

Turning on --noUncheckedIndexedAccess can also type typed-array indexing as number | undefined. In a project using that setting, narrow the value into a local variable after #nodeError(); a bounds check does not make the compiler narrow later array accesses for you.

Two trees of equal size

The comparison in attachSmallerRoot() is <, so when two components are the same size no swap happens and right goes under left. At equal size either side can be the root with the same height bound on the resulting tree, which means the tie-break can be arbitrary. Switching it to <= leaves correctness and amortized complexity unchanged.

What does change is which side becomes the root, so a test that expects a specific root value is a sign it is checking the wrong thing.

3. Call Site

External server IDs are strings, so a separate index layer turns them into 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, while an empty snapshot is a normal result rather than an error, so the call site keeps a separate branch that returns an empty index before calling DisjointSet.create(). Fold that into a DisjointSet | null field and every lookup path ends up with a null check that can never be true. When the node map is empty, requireNode() returns an unknown-server-id error; splitting the implementation in two removes that branch from the lookup path.

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

Union-Find's root index is not exposed in the external API, because the root is internal implementation information that a later union can change.

connectLink() and #getNode() share the same requireNode(), so the unknown-server-ID error code sits in one place for both the loading and the lookup side. If buildConnectivityIndexAsync() returned only the Map and dropped DisjointSet as a local variable, no connectivity information would survive despite the name — the return value has to hold DisjointSet for 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 you compare, keep the measurement axes separate too.

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.)

Cache a ConnectivityIndex for the whole process lifetime and this map stays alive with it. The lifetime policy is something the call site decides, not the data structure.

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

This is not a place to blur that lifetime with WeakRef or FinalizationRegistry; 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 this.

Text

parent[rootOfSmallerComponent]
= rootOfLargerComponent

Don't link the elements themselves — link their representative roots.

5. Misconceptions That Arise in Practice

Union-Find cannot handle edge deletion

In the following graph, deleting 1—2 can split the component in two.

Text

0 — 1 — 2 — 3

But Union-Find holds no information about which edge joined two sets, so the options split as follows.

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 state right now is this.

Text

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

Merging two sets changes the root of the smaller set because of union-by-size.

Text

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

Use the root as a DB key or a group ID shown to users, and the identifier changes on a later union. If the business needs a stable group ID, keep a separate canonical ID policy.

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

After merging, I didn't bother resetting the size of the smaller root to 0.

Text

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

Valid lookup:

Text

componentSize[find(2)]

Invalid lookup:

Text

componentSize[2]

This is another reason the internal arrays are never handed out.

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

Path compression rewrites 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

Otherwise pick an actor, a lock, or partitioned ownership.

Rollback and path shortening do not mix well

This one matters, so I'm writing it 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, it usually goes like this:

Text

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

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

Do not use external IDs directly as array indices

Sizing an array to fit the next ID is pure waste.

Text

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

You have only 3 actual elements, yet the array has to cover the largest ID.

Text

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

Union-Find only gets array efficiency when the index space is dense.

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 both are already in 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, so check it.

Memory usage is O(N)

Two arrays, 32-bit parent and size, come to 8 bytes of raw storage per element, and I checked that myself.

Text

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

A Python object list can carry far more overhead for the same logical structure (I measured it). And as seen earlier, a string ID map can be an order of magnitude larger than that raw storage. For large inputs, measure real memory 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],
    );
  }
}

Look at the following calls.

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

You get a cycle instead of a parent forest, and find(0) never terminates — this is an example I wrote when I first started learning.

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 links any two 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

Ran it with the LCG seeds 0x5eed, 0x1, and 0xdeadbeef: 128 nodes, 20,000 unions, and 8 connectivity queries after every union.

That is 160,000 queries per seed; the numbers below come from 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.

In C# and TypeScript, invalid-node came back for negative nodes and nodes past the upper bound, and invalid-element-count for 0 and 10,000,001. Running the Python implementation also showed 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) let this test file pass as-is even in projects with --noUncheckedIndexedAccess enabled. Failing the test immediately instead of substituting another node for undefined shows explicitly whether the reference implementation has a defect.

A programmer should always write it down explicitly, because it saves you from confusion when you look again 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

Union-Find itself may be fast, but hashing a string ID on every call can cost more, so measure the whole 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 give good locality and clear ownership. The catch is that findRoot() mutates the parent array, so even shared reads need synchronization.

uint32_t puts a clear cap on the maximum element count. Using size_t unconditionally can double parent array memory in a 64-bit environment, so pick the index width to match the real maximum scale.

Member initialization following declaration order is a trap only this language has. Keep the constructor from Chapter 2 and just reorder the member declarations, and it silently becomes undefined behavior.

Python

The algorithm is the same, but list[int] is not a packed 32-bit integer array: every list slot and every integer object carries representation cost.

If millions of elements are the bottleneck, consider this.

Text

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

Still, if the Python loop is the hot path, changing only the storage representation may not be enough.

C#

Two int[] arrays are compact, and the GC doesn't track each element as a separate object. At 10 million elements one array is 40 MB and lands on the large object heap, so with large arrays you look at the managed heap policy and snapshot lifetime together.

AreConnected() and GetComponentSize() read like read operations by name, but they modify the array through path halving. Writing that down in the API docs, or adding a separate read-only snapshot type, is probably the crux of the API design.

TypeScript

Int32Array stores parent and size at a fixed width. The intent is clearer than a plain number[], and no sparse holes appear.

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.

Uint32Array, though, doesn't seem to block negative assignment at the type level (checked with a test).

The element type is still number: values[0] = -1 is accepted and stored as 4_294_967_295 after the ToUint32 conversion, so boundary validation like #nodeError() still seems necessary with an unsigned array. Choosing between Int32Array and Uint32Array is a question of storage representation and sentinel policy.

In a real service, though, costs like these can be larger.

Text

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

If queries are heavy, cache a validated NodeId handle inside the upper-level session so callers don't pass a string every time.

Common contract

In the end, these are the points every implementation here has to line up on.

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 deletion happens once a day, wouldn't a full rebuild be simpler and faster than a dynamic connectivity structure?
How do you reliably attach per-component business metadata without exposing the root?
For parallel ingestion, which fits the actual workload: one concurrent DSU, or a local DSU per worker merged later?
When rollback is required and path compression has to go, what change history do you keep on the stack?
With string external IDs, does the Map lookup cost outgrow the Union-Find operations themselves?
If you need the actual connection path, will you pay the memory to keep both Union-Find and an adjacency graph?
If measurements show the string index is bigger than the data structure itself, who owns that index and when is it dropped?
How do you turn Result error codes into HTTP, CLI, and job-queue responses at the call site?

10. Summary

Union-Find tracks the connected components of a graph efficiently as edges are added.
union has to 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 IDs.
areConnected() and getComponentSize() are write operations despite their names.
Edge deletion, actual path retrieval, and concurrent modification are outside what a basic Union-Find is responsible for.
Size validation has to come before array allocation, and in C++ that order depends on member declaration order.
What dominates real memory may be the external ID map, not the integer arrays.
Correctness is verified by checking random operations against BFS results on a reference graph.

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 is designing the fast algorithm and the object allocation model together, not separately. Swap the algorithm and the outer structure mostly survives and gets reused, as long as input validation, failure contracts, state ownership, and call boundaries hold. What changes is the internal data structure and the performance profile — in the end, failure contracts and state ownership are where a programmer's style shows.

Footnotes

The trade-off is a narrow feature set: Union-Find tells you whether two elements are connected, but not the actual connection path.

It also cannot directly handle an edge deletion that splits a component. If you need deletions, rebuild from scratch, process offline with a rollback DSU, or use a dynamic connectivity 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

Suppose a network management system receives connection information between servers in order.

Text

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

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

At first, every server is its own component.

Text

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

Applying 0—1 and 1—2 gives this.

Text

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

Applying 3—4 as well gives this.

Text

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

Finally, applying 2—4 merges the two components into one.

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

The implementation assumes element IDs are dense integers in 0..N-1. UUIDs and string IDs are converted to integer indexes at the call boundary.

2. Core Representation

Error Handling

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.

Constructor initialization order

If validation sits in the constructor body, both vector allocations have already been attempted by then. componentCount_ is a single size_t value, so it needs no dynamic allocation of its own.

C++

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

C++

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

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)

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() checks the element count before allocating the arrays, and the private constructor takes only validated values, so predictable input errors never turn into exceptions.

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 pins down the storage format and element width more firmly than a plain number[]. At this upper bound, neither component sizes nor parent indexes exceed the signed 32-bit range.

This was written with --strict and --noUnusedLocals enabled.

Two trees of equal size

What does change is which side becomes the root, so a test that expects a specific root value is a sign it is checking the wrong thing.

3. Call Site

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

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

Union-Find's root index is not exposed in the external API, because the root is internal implementation information that a later union can change.

Lifetime of the index

When you compare, keep the measurement axes separate too.

Text

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

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

Cache a ConnectivityIndex for the whole process lifetime and this map stays alive with it. The lifetime policy is something the call site decides, not the data structure.

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

This is not a place to blur that lifetime with WeakRef or FinalizationRegistry; 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 this.

Text

parent[rootOfSmallerComponent]
= rootOfLargerComponent

Don't link the elements themselves — link their representative roots.

5. Misconceptions That Arise in Practice

Union-Find cannot handle edge deletion

In the following graph, deleting 1—2 can split the component in two.

Text

0 — 1 — 2 — 3

But Union-Find holds no information about which edge joined two sets, so the options split as follows.

Text

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

It does not provide the actual connection path

Text

areConnected(0, 7)
→ true

Root is not a stable component ID

Suppose the state right now is this.

Text

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

Merging two sets changes the root of the smaller set because of union-by-size.

Text

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

Use the root as a DB key or a group ID shown to users, and the identifier changes on a later union. If the business needs a stable group ID, keep a separate canonical ID policy.

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

After merging, I didn't bother resetting the size of the smaller root to 0.

Text

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

Valid lookup:

Text

componentSize[find(2)]

Invalid lookup:

Text

componentSize[2]

This is another reason the internal arrays are never handed out.

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

Path compression rewrites the parent pointers.

Text

Before compression:
7 → 5 → 3 → 0

find(7)

After compression (example):
7 → 3 → 0

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

Otherwise pick an actor, a lock, or partitioned ownership.

Rollback and path shortening do not mix well

This one matters, so I'm writing it in red.

If rollback is a core requirement, it usually goes like this:

Text

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

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

Do not use external IDs directly as array indices

Sizing an array to fit the next ID is pure waste.

Text

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

You have only 3 actual elements, yet the array has to cover the largest ID.

Text

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

Union-Find only gets array efficiency when the index space is dense.

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 both are already in 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, so check it.

Memory usage is O(N)

Two arrays, 32-bit parent and size, come to 8 bytes of raw storage per element, and I checked that myself.

Text

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

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],
    );
  }
}

Look at the following calls.

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

You get a cycle instead of a parent forest, and find(0) never terminates — this is an example I wrote when I first started learning.

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 links any two 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

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

Ran it with the LCG seeds 0x5eed, 0x1, and 0xdeadbeef: 128 nodes, 20,000 unions, and 8 connectivity queries after every union.

That is 160,000 queries per seed; the numbers below come from 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

Text

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

Points that are problematic in testing.

A programmer should always write it down explicitly, because it saves you from confusion when you look again 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

Union-Find itself may be fast, but hashing a string ID on every call can cost more, so measure the whole 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 give good locality and clear ownership. The catch is that findRoot() mutates the parent array, so even shared reads need synchronization.

Python

The algorithm is the same, but list[int] is not a packed 32-bit integer array: every list slot and every integer object carries representation cost.

If millions of elements are the bottleneck, consider this.

Text

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

Still, if the Python loop is the hot path, changing only the storage representation may not be enough.

C#

TypeScript

Int32Array stores parent and size at a fixed width. The intent is clearer than a plain number[], and no sparse holes appear.

Uint32Array, though, doesn't seem to block negative assignment at the type level (checked with a test).

In a real service, though, costs like these can be larger.

Text

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

If queries are heavy, cache a validated NodeId handle inside the upper-level session so callers don't pass a string every time.

Common contract

In the end, these are the points every implementation here has to line up on.

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 deletion happens once a day, wouldn't a full rebuild be simpler and faster than a dynamic connectivity structure?
How do you reliably attach per-component business metadata without exposing the root?
For parallel ingestion, which fits the actual workload: one concurrent DSU, or a local DSU per worker merged later?
When rollback is required and path compression has to go, what change history do you keep on the stack?
With string external IDs, does the Map lookup cost outgrow the Union-Find operations themselves?
If you need the actual connection path, will you pay the memory to keep both Union-Find and an adjacency graph?
If measurements show the string index is bigger than the data structure itself, who owns that index and when is it dropped?
How do you turn Result error codes into HTTP, CLI, and job-queue responses at the call site?

10. Summary

Union-Find tracks the connected components of a graph efficiently as edges are added.
union has to 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 IDs.
areConnected() and getComponentSize() are write operations despite their names.
Edge deletion, actual path retrieval, and concurrent modification are outside what a basic Union-Find is responsible for.
Size validation has to come before array allocation, and in C++ that order depends on member declaration order.
What dominates real memory may be the external ID map, not the integer arrays.
Correctness is verified by checking random operations against BFS results on a reference graph.

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 is designing the fast algorithm and the object allocation model together, not separately. Swap the algorithm and the outer structure mostly survives and gets reused, as long as input validation, failure contracts, state ownership, and call boundaries hold. What changes is the internal data structure and the performance profile — in the end, failure contracts and state ownership are where a programmer's style shows.

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

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

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

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