src/set.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <stdlib.h>

#include "set.h"

set *set_create()
{
    set *s = malloc(sizeof(set));
    s->parent = s;
    s->rank = 0;
    return s;
}

void set_free(set *s)
{
    free(s);
}

set *set_find(set *s)
{
    if(s->parent == s)
        return s;
    s->parent = set_find(s->parent);
    return s->parent;
}

void set_union(set *x, set *y)
{
    x = set_find(x);
    y = set_find(y);

    if(x == y) return;

    if(x->rank > y->rank) {
        y->parent = x;
    } else {
        x->parent = y;
    }

    if(x->rank == y->rank) x->rank++;
}