不相交集实现实例

/* disjoint_set.h */

#ifndef _DISJOINT_SET_H
#define _DISJOINT_SET_H

#define NUMSETS    5
typedef int disjoint_set[NUMSETS + 1];
typedef int set_type;
typedef int element_type;

void initialize(disjoint_set s);
void set_union(disjoint_set s, set_type root1, set_type root2);
set_type find(element_type x, disjoint_set s);

#endif /* _DISJOINT_SET_H */

/* disjoint_set.c */

#include "disjoint_set.h"

void 
initialize(disjoint_set s)
{
    int i;
    
    for(i = NUMSETS; i > 0; i--)
        s[i] = 0;
}

void 
set_union(disjoint_set s, element_type x1, element_type x2)
{
    set_type root1, root2;
    root1 = find(x1, s);
    root2 = find(x2, s);
    s[root2] = root1;
}

set_type 
find(element_type x, disjoint_set s)
{
    if(s[x] <= 0)
        return x;
    else
        return find(s[x], s);
}

/* disjoint_set_test.c */

#include "disjoint_set.h"
#include <stdio.h>

int
main(void)
{
    disjoint_set s;
    initialize(s);
    set_union(s, 1, 2);
    set_union(s, 3, 4);
    set_union(s, 5, 1);
    set_union(s, 4, 2);

    if(find(1, s) == find(3, s))
        printf("1 and 3 are joint\n");
    else
        printf("1 and 3 are not joint\n");
    
    return 0;
}

/* Makefile */

target := test
objs := disjoint_set_test.o disjoint_set.o  
$(target):$(objs)
    gcc -o $@ $^
%.o:%.c
    gcc -c -o $@ $<

clean:
    rm *.o test