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  )

inlinestatic

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  )

inlinestatic

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  )

inlinestatic

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.