Disjoint-Sets Forest with path-compression and union-by-rank

DisjointSetsForest.c

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

typedef struct Set {
    struct Set* parent;
    int value;
    int rank;
} Set;

Set* MakeSet(int value)
{
    // x must not already be in some other set
    Set* x = (Set*)malloc(sizeof(Set));
    x->parent = x;
    x->value = value;
    x->rank = 0;
    return x;
}

Set* FindSet(Set* x)
{
    assert(x);

    if (x->parent == x)
        return x;

    x->parent = FindSet(x->parent);
    return x->parent;
}

void Link(Set* x, Set* y)
{
    assert(x);
    assert(y);
    if (x->rank <= y->rank) {
        x->parent = y;
        if (x->rank == y->rank)
            y->rank += 1;
    } else {
        y->parent = x;
    }
}

void Union(Set* x, Set* y)
{
    assert(x);
    assert(y);
    Link(FindSet(x), FindSet(y));
}


int main(int argc, char** argv)
{
    Set* c = MakeSet(10);
    Set* h = MakeSet(11);
    Set* e = MakeSet(12);
    Set* b = MakeSet(13);

    Union(e, c);
    Union(h, b);
    Union(h, c);
    printf("FindSet(e) == %d, rank %d\n", FindSet(e)->value, FindSet(e)->rank);

    Set* f = MakeSet(14);
    Set* d = MakeSet(15);
    Set* g = MakeSet(16);
    printf("FindSet(g) == %d, rank %d\n", FindSet(g)->value, FindSet(g)->rank);

    Union(d, g);
    Union(f, d);

    Union(e, g);
    printf("FindSet(e) == %d, rank %d\n", FindSet(e)->value, FindSet(e)->rank);

    assert(FindSet(c) == FindSet(h));
    assert(FindSet(h) == FindSet(e));
    assert(FindSet(e) == FindSet(b));
    assert(FindSet(b) == FindSet(f));
    assert(FindSet(f) == FindSet(d));
    assert(FindSet(d) == FindSet(g));
    assert(FindSet(g) == FindSet(c));

    free(c);
    free(h);
    free(e);
    free(b);
    free(f);
    free(d);
    free(g);

    return 0;
}