Exports a UnionFind data structure exposed as an Rcpp Module.
union_find(size)
| size | the size of the disjoint set |
|---|
A queryable disjoint-set structure.
UnionFind, also called a disjoint-set, is a data structure that allows efficient tracking and unioning of elements in terms of connected components. To use the structure, instantiate it with a given (fixed) size of components, and then union or find as needed. This implementation uses path compression to speed up successive find operations.
union Unions two elements together.
union_all Unions all the elements in a given vector together.
find Find which components a given element is associated with. If the elements given doesn't exist, -1 is returned.
find_all Finds which component each element in a given vector is associated with. If the elements given doesn't exist, -1 is returned.
print Prints the connected components.
connected_components Retrieves the connected components as a integer vector.
Tarjan, Robert Endre. "Efficiency of a good but not linear set union algorithm." Journal of the ACM (JACM) 22.2 (1975): 215-225.