When a Bag of Rings Becomes One Object

Yesterday I closed forty rings into something the size of a loonie and called it a start. European 4-in-1: every ring threads through four neighbours, and the whole idea is that you can’t lift a single ring without the rest following. That property has a name — connectivity — and there’s an algorithm whose entire job is to answer one question about it: are these two things part of the same piece?

The structure is a disjoint-set forest. You keep an array where each ring points at another ring in its group. Follow the pointers upward and you land on a representative. Two rings belong to the same sheet when they reach the same representative. Closing a ring that bridges two separate chains is a union: aim one group’s root at the other’s.

(define (make-uf n)
  (let ((p (make-vector n)))
    (do ((i 0 (+ i 1))) ((= i n) p) (vector-set! p i i))))
(define (find p x)
  (if (= (vector-ref p x) x) x
      (let ((r (find p (vector-ref p x))))
        (vector-set! p x r) r)))              ; path compression
(define (union p a b) (vector-set! p (find p a) (find p b)))

(define maille (make-uf 5))
(union maille 0 1) (union maille 1 2) (union maille 3 4)
(display (= (find maille 0) (find maille 2))) (newline)  ; #t — same chain
(display (= (find maille 0) (find maille 4))) (newline)  ; #f — off on its own

What makes it quick is inside find: as it walks back out, it rewrites each ring’s pointer to aim straight at the root. Path compression — flatten the tree while you read it, so the next lookup is nearly instant. Robert Tarjan and Jan van Leeuwen pinned down the worst-case cost in 1984: near-constant per operation, scaling with the inverse Ackermann function, which for any pile of rings you could physically close sits at effectively 4.

class Maille {
    int[] p;
    Maille(int n) { p = new int[n]; for (int i = 0; i < n; i++) p[i] = i; }
    int find(int x) { return p[x] == x ? x : (p[x] = find(p[x])); } // path compression
    void weave(int a, int b) { p[find(a)] = find(b); }              // union two chains

    public static void main(String[] args) {
        Maille m = new Maille(5);
        m.weave(0, 1); m.weave(1, 2); m.weave(3, 4);
        System.out.println(m.find(0) == m.find(2)); // true  — one connected scrap
        System.out.println(m.find(0) == m.find(4)); // false — a detached bit
    }
}

Run either and you get true then false: rings 0 through 2 are one connected scrap, ring 4 is stranded — exactly the detached loop I keep making when I drop a ring and don’t notice for six rows. Percolation researchers reach for this to ask when a random lattice suddenly spans edge to edge. A maille sheet carries the same yes/no inside it: keep unioning until find agrees on everything, and the bag of loops has turned into a single object.