Disjoint Sets

disjoint_set.c

#include "disjoint_set.h"

void disjoint_set_new(disjoint_set_t *set) {
    set->parent = set;
    set->rank = 0;
}

disjoint_set_t *disjoint_set_find(disjoint_set_t *set) {
    disjoint_set_t *root = set->parent;

    while (root != root->parent)
        root = root->parent;

    set->parent = root;

    return root;
}

void disjoint_set_union(disjoint_set_t *set_1, disjoint_set_t *set_2) {
    disjoint_set_t *root_1 = disjoint_set_find(set_1);
    disjoint_set_t *root_2 = disjoint_set_find(set_2);

    if (root_1 == root_2)
        return;

    if (root_1->rank > root_2->rank) {
        root_2->parent = root_1->parent;
    } else if (root_1->rank < root_2->rank) {
        root_1->parent = root_2->parent;
    } else {
        root_1->parent = root_2->parent;
        root_2->rank++;
    }
}

int disjoint_set_same(disjoint_set_t *set_1, disjoint_set_t *set_2) {
    return disjoint_set_find(set_1) == disjoint_set_find(set_2);
}

disjoint_set.h

#ifndef DISJOINT_SET_H
#define DISJOINT_SET_H

/*
    Disjoint Set

    Sets that support only creation and merging.
    
    disjoint_set_make creates a set of a single item    
    disjoint_set_union joins the two sets that the arguments belong to
    disjoint_set_same returns true iff the two items are contained in the same set

    No memory is allocated, your structures should contain a disjoint_set_t,
    and structures of different types may belong to the same set.
*/

typedef struct disjoint_set_s disjoint_set_t;
struct disjoint_set_s {
    disjoint_set_t *parent;
    int rank;
};

void disjoint_set_new(disjoint_set_t *);
void disjoint_set_union(disjoint_set_t *, disjoint_set_t *);
int disjoint_set_same(disjoint_set_t *, disjoint_set_t *);

#endif