# Disjoint Set Union (DSU)

Union-find data structure for tracking connected components. Implements the `DSU<K>` interface: `find`, `union`, `connected`, `groupSize`, `numGroups`, `clear`.

Does **not** extend `Collection` — DSU has no meaningful iteration order.

## Implementations

### ArrayDSU

Array-backed DSU for numeric indices `0..N-1`. Uses union-by-size and path halving for near-O(1) amortized operations.

| Operation   | Best | Average   | Worst    |
| :---------- | :--- | :-------- | :------- |
| Space       | O(n) | O(n)      | O(n)     |
| `find`      | O(1) | O(α(n))\* | O(log n) |
| `union`     | O(1) | O(α(n))\* | O(log n) |
| `connected` | O(1) | O(α(n))\* | O(log n) |
| `groupSize` | O(1) | O(α(n))\* | O(log n) |

\* α(n) is the inverse Ackermann function — effectively constant for all practical inputs.

**Strengths:** Minimal memory (two flat arrays). Cache-friendly. Near-O(1) amortized for all operations via union-by-size + path halving.

**Weaknesses:** Keys must be contiguous integers `0..N-1`. Fixed size at construction.

### KeyDSU

Map-backed DSU for arbitrary key types. Uses union-by-size and path halving, same as ArrayDSU.

| Operation   | Best | Average   | Worst    |
| :---------- | :--- | :-------- | :------- |
| Space       | O(n) | O(n)      | O(n)     |
| `find`      | O(1) | O(α(n))\* | O(log n) |
| `union`     | O(1) | O(α(n))\* | O(log n) |
| `connected` | O(1) | O(α(n))\* | O(log n) |
| `groupSize` | O(1) | O(α(n))\* | O(log n) |

\* Same amortized bound. Map lookups add a constant factor vs array indexing.

**Strengths:** Accepts any key type — strings, objects, symbols. Keys provided at construction via iterable. Deduplicates automatically (Map semantics).

**Weaknesses:** Higher constant factor than ArrayDSU due to Map overhead. Fixed key set at construction.

## Which to use

| Use case                   | Recommendation                                       |
| :------------------------- | :--------------------------------------------------- |
| Numeric indices `0..N-1`   | **ArrayDSU** — lower constant factor, cache-friendly |
| String / object keys       | **KeyDSU** — the only option for non-numeric keys    |
| Unknown key count at start | **KeyDSU** — accepts any iterable of keys            |

**Default choice: ArrayDSU** when keys are numeric indices. **KeyDSU** when they're not.

## Usage

```typescript
import { ArrayDSU, KeyDSU } from "@coda/data-structures";

// Numeric indices
const dsu = new ArrayDSU(10);
dsu.union(0, 1);
dsu.union(1, 2);
dsu.connected(0, 2); // true
dsu.groupSize(0); // 3
dsu.numGroups; // 8

// Arbitrary keys
const kdsu = new KeyDSU(["alice", "bob", "carol"]);
kdsu.union("alice", "bob");
kdsu.connected("alice", "bob"); // true
kdsu.find("carol"); // 'carol' (own root)
```