Union-Find

Union-Find data structure. More...

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

Detailed Description

Union-Find data structure.

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 *const  data, int const  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 83 of file unionfind.h.

static void uf_init ( int *const  data, size_t const  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 data structure

Definition at line 35 of file unionfind.h.

static int uf_union ( int *const  data, int const  set1, int const  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 51 of file unionfind.h.