Union-Find 기반 증분 연결성 추적

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

find(x)
= x가 속한 집합의 root

union(a, b)
= root(a)와 root(b)가 다르면
  작은 컴포넌트를 큰 컴포넌트 아래에 연결

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

핵심 불변식:

root인 원소:
parent[root] == root

모든 원소:
parent를 반복해서 따라가면
정확히 하나의 root에 도달

componentSize[root]
= 해당 root가 대표하는 원소 수

서버:
0, 1, 2, 3, 4, 5

신규 연결:
0 — 1
1 — 2
3 — 4
2 — 4

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

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

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

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

0과 4는 연결되어 있는가?
→ true

0과 5는 연결되어 있는가?
→ false

3이 속한 컴포넌트 크기는?
→ 5

현재 독립 컴포넌트 수는?
→ 2

#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;
    }
};

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

explicit DisjointSet(std::size_t elementCount)
    : parent_(elementCount),
      componentSize_(elementCount, 1),
      componentCount_(elementCount)
{
    validateElementCount(elementCount); // 너무 늦다.
}

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

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)

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)

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;
    }
}

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

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;
}

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;
}

NetworkSource
= 서버와 link snapshot I/O

Node Index
= 외부 문자열 ID
→ 조밀한 정수 index 변환

DisjointSet
= 정수 원소의 연결 컴포넌트 관리

ConnectivityIndex
= 업무 ID 기반 조회 API

Snapshot Builder
= Load → Validate → Map → Union

Rebuild Policy
= link 삭제나 snapshot version 변경 처리

Map/string delta:
heapUsed 기준 약 119.5 MiB

Int32Array 두 개, 원소 100만 개:
arrayBuffers 기준 약 7.6 MiB

- 요청 단위 인덱스: 응답 후 참조를 끊는다
- 장기 캐시: snapshot version과 TTL을 함께 둔다
- 재구축: 새 인덱스를 만든 뒤 참조를 교체한다
- 조회가 많으면: 검증된 정수 handle을 상위 세션이 들고 있게 한다

원소 ID가 0..N-1로 조밀한가
→ parent[i]가 유효한 index인가
→ 초기 parent[i]가 i인가
→ find가 root까지 이동하는가
→ find 과정에서 경로를 압축하는가
→ union 전에 양쪽 root를 찾는가
→ 이미 같은 root면 상태를 바꾸지 않는가
→ 작은 컴포넌트를 큰 컴포넌트에 붙이는가
→ size는 새 root에만 더하는가
→ componentCount는 실제 병합 때만 감소하는가
→ 크기 검증이 배열 할당보다 먼저 일어나는가
→ root를 외부의 영구 ID로 노출하지 않는가

parent[right] = left

parent[rootOfSmallerComponent]
= rootOfLargerComponent

0 — 1 — 2 — 3

삭제 대응 선택지:
- 전체 snapshot에서 재구축
- 시간 순서를 뒤집은 offline 처리
- Rollback DSU
- 완전 동적 연결성 자료구조

areConnected(0, 7)
→ true

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

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

parent[2] = 0
componentSize[2] = 과거 값

componentSize[find(2)]

componentSize[2]

압축 전:
7 → 5 → 3 → 0

find(7)

압축 후 예:
7 → 3 → 0

Build 단계:
단일 owner가 union과 path halving 수행

Publish 단계:
모든 경로를 압축한 immutable snapshot 생성

Read 단계:
수정하지 않는 root lookup 사용

- union-by-size 유지
- path halving을 포함한 경로 단축 생략
- 변경된 parent와 size만 stack에 기록

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

외부 ID
→ dense index mapping
→ 0, 1, 2

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

false 의미:
입력이 잘못됨
아님

false 의미:
새로운 컴포넌트 병합이 없었음

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

- 원소끼리 직접 parent를 연결해 cycle을 만듦
- Union 전에 root를 찾지 않음
- Root를 영구적인 business ID로 저장함
- 일반 node의 size slot을 직접 읽음
- Edge 삭제를 union의 반대 연산으로 처리함
- 외부 64-bit ID를 배열 index로 그대로 사용함
- 동시 find가 read-only라고 가정함
- Rollback DSU에 path halving을 포함한 경로 단축을 사용함
- 중복 union 때 componentCount를 감소시킴
- 실제 경로를 얻기 위해 parent forest를 graph path로 해석함
- 크기 검증 전에 배열을 먼저 할당함
- 문자열 index의 수명을 아무도 소유하지 않음

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

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

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

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

0 → 2 → 1 → 0

- left와 right의 root를 찾지 않는다.
- 이미 연결된 집합인지 검사하지 않는다.
- union-by-size 또는 rank가 없다.
- path halving을 포함한 경로 단축이 없다.
- 재귀 호출이 긴 chain에서 stack을 소비한다.
- index 범위 검증이 없다.
- 컴포넌트 크기와 개수를 추적할 수 없다.
- cycle이 발생해도 감지하지 않는다.

잘못된 의미:
right의 parent를 left로 설정

올바른 의미:
right가 속한 집합의 root와
left가 속한 집합의 root를 병합

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

test("Union-Find는 기준 graph 연결성과 같다", () =>
{
  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("chain, star, balanced 병합 순서에서도 component 크기를 보존한다", () =>
{
  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("중복 union은 component 수를 줄이지 않는다", () =>
{
  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("컴포넌트 크기는 실제 원소 수와 같다", () =>
{
  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("범위를 벗어난 입력은 Result 오류다", () =>
{
  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;
  };
}

실제 병합:                127회
이미 연결된 no-op:      19,873회
선택된 서로 다른 node:    128개
최종 component 수:          1개
node 0의 component 크기:   128개

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

초기 상태:
componentCount == N

실제 병합:
componentCount는 정확히 1 감소

중복 병합:
componentCount는 변하지 않음

모든 node:
areConnected(node, node) == true

같은 컴포넌트의 모든 node:
getComponentSize(node)가 동일

모든 union 이후:
Reference BFS 연결성과 동일

빈 snapshot:
getComponentCount() == 0이고 조회는 Result 오류

1. 매 질의마다 BFS·DFS
2. Union-Find without optimization
3. Union-by-size만 적용
4. Union-by-size + path halving

- 원소 수 N
- Union과 Query 비율
- 중복 edge 비율
- 입력 순서
- 컴포넌트 크기 분포
- 외부 ID mapping 비용
- 메모리 사용량

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

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

공통 계약:
- 원소 ID 범위
- 초기 컴포넌트 정의
- union-by-size 규칙
- 경로 단축 방식 (compression, splitting, halving 중 무엇인지)
- 중복 union 반환 의미
- root 비공개 정책
- edge 삭제 정책
- 동시성 소유권
- 검증과 할당의 순서

원소를 직접 연결하지 마라.
각 원소의 root를 찾고,
작은 컴포넌트의 root만
큰 컴포넌트의 root 아래에 붙여라.