Union-Find

Union-Find datastructure. More...

Functions
static void	uf_init (int *data, size_t n_elems)
	Call this to initialize an array of count elements to be used by the union find functions.
static int	uf_union (int *data, int set1, int set2)
	Merge 2 sets (union operation).
static int	uf_find (int *data, int e)
	Finds the representative for the set with member e.

---

Detailed Description

Union-Find datastructure.

This implementation uses weighted sets and path compression which results in (nearly) O(n) complexity for n find and union operations

---

Function Documentation

static int uf_find	(	int *	data,
		int	e
	)		[inline, static]

Finds the representative for the set with member e.

The representative of a set is unique, so if the find operations finds the same/different representatives, then the elements are in the the same/different sets.

Parameters:

data	The union find data
e	The element

Returns:

The representative of the set that contains e

Definition at line 102 of file unionfind.h.

static void uf_init	(	int *	data,
		size_t	n_elems
	)		[inline, static]

Call this to initialize an array of count elements to be used by the union find functions.

Parameters:

data	The array (you have to allocate it yourself)
n_elems	number of elements handled by the datastructure

Definition at line 49 of file unionfind.h.

static int uf_union	(	int *	data,
		int	set1,
		int	set2
	)		[inline, static]

Merge 2 sets (union operation).

Note that you have to pass the representatives of the sets and not just random elements

Parameters:

data	The union find data
set1	Representative of set1
set2	Representative of set2

Returns:

the new representative of the set (which is set1 or set2)

Definition at line 66 of file unionfind.h.