Disjoint set union/find

dsu.c

#include <stdio.h>
#include <stdlib.h>

typedef struct node_s {
  struct node_s *parent;
  int size;
  int value;
} DISJOINT_SET;

DISJOINT_SET *make_set(int value) {
  DISJOINT_SET *s = malloc(sizeof *s);
  s->parent = s;
  s->size = 1;
  s->value = value;
  return s;
}

DISJOINT_SET *find(DISJOINT_SET *elt) {
  DISJOINT_SET *s, *p;
  for (s = elt; s != s->parent; s = s->parent) /* skip */;
  for (p = elt; p != p->parent; p = p->parent) p->parent = s;
  return s;
}

DISJOINT_SET *make_union(DISJOINT_SET *a, DISJOINT_SET *b) {
  a = find(a);
  b = find(b);
  if (a == b) return a;
  if (b->size > a->size) {
    a->parent = b;
    b->size += a->size;
    return b;
  }
  b->parent = a;
  a->size += b->size;
  return a;
}

int locate(DISJOINT_SET **a, int n, int p) {
  for (int i = 0; i < n; ++i, ++p) {
    if (p >= n) p = 0;
    if (a[p]) return p;
  }
  return -1;
}

int main(void) {
  int n = 100000;
  DISJOINT_SET *s[n], *r[n];

  for (int i = 0; i < n; ++i) s[i] = r[i] = make_set(i);
  for (;;) {
    int elt_a = locate(s, n, rand() % n);
    int elt_b = locate(s, n, rand() % n);
    if (elt_a == elt_b) continue;
    s[elt_a] = make_union(s[elt_a], s[elt_b]);
    s[elt_b] = NULL;
    if (s[elt_a]->size == n) break;
  }
  DISJOINT_SET *x = find(r[0]);
  for (int i = 1; i < n; ++i)
    if (find(r[i]) != x) {
      printf("oops: %d\n", r[i]->value);
      break;
    }

  return 0;
}