Skip to content

Instantly share code, notes, and snippets.

@vwood
Created February 8, 2012 09:32
Show Gist options
  • Save vwood/1767180 to your computer and use it in GitHub Desktop.
Save vwood/1767180 to your computer and use it in GitHub Desktop.
Disjoint Sets
#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);
}
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment