Optimized Disjoint Set Union (Union-Find) for Grid Connectivity

A high-performance C implementation of a Disjoint Set Union (DSU) system for discovering connected regions in 2-D grids.
Designed for large datasets such as image masks, percolation maps, and maze structures.

This DSU combines:

• Union-by-Size and Path-Halving for near-constant-time merges and finds
• Contiguous memory layout for cache-efficient performance
• Linked-member tracking to enumerate all cells in a connected region directly
• A clean, modular API for easy integration into other projects

---

🔧 Features

• Handles millions of grid cells efficiently (e.g. 2500×2500)
• One-pass connected region detection
• Fast union/find operations (≈ O(α(n)))
• Enumerate regions in O(region size)
• Lightweight pure-C library (no external dependencies)

---

🧩 Usage Example

#include "dsu.h"
#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint32_t w = 5, h = 5;
    uint8_t grid[] = {
        1,1,0,0,0,
        1,1,0,1,1,
        0,0,0,1,1,
        1,0,0,0,0,
        1,1,1,0,0
    };

    DSU *dsu = dsu_new(w * h);

    // Connect neighboring cells with the same value
    for (uint32_t y = 0; y < h; ++y) {
        for (uint32_t x = 0; x < w; ++x) {
            uint32_t idx = y * w + x;
            if (x + 1 < w && grid[idx] == grid[idx + 1])
                dsu_union(dsu, idx, idx + 1);
            if (y + 1 < h && grid[idx] == grid[idx + w])
                dsu_union(dsu, idx, idx + w);
        }
    }

    // Example: count unique connected regions
    uint32_t *roots = calloc(w * h, sizeof(uint32_t));
    uint32_t count = 0;
    for (uint32_t i = 0; i < w * h; ++i) {
        uint32_t root = dsu_find(dsu, i);
        if (!roots[root]) {
            roots[root] = 1;
            count++;
        }
    }
    printf("Found %u connected regions.\n", count);

    free(roots);
    dsu_free(dsu);
    return 0;
}