# NAME

Graph::UnionFind - union-find data structures

# SYNOPSIS

``````    use Graph::UnionFind;
my \$uf = Graph::UnionFind->new;

# Add the vertices to the data structure.

# Join the partitions of the vertices.
\$uf->union( \$u, \$v );

# Find the partitions the vertices belong to
# in the union-find data structure.  If they
# are equal, they are in the same partition.
# If the vertex has not been seen,
# undef is returned.
my \$pu = \$uf->find( \$u );
my \$pv = \$uf->find( \$v );
\$uf->same(\$u, \$v) # Equal to \$pu eq \$pv.

# Has the union-find seen this vertex?
\$uf->has( \$v )``````

# DESCRIPTION

Union-find is a special data structure that can be used to track the partitioning of a set into subsets (a problem also known as disjoint sets).

`Graph::UnionFind` is used for "connected_components" in Graph, "connected_component" in Graph, and "same_connected_components" in Graph if you specify a true `unionfind` parameter when you create an undirected graph.

Union-find is one way: you cannot (easily) 'ununion' vertices once you have 'unioned' them. This is why Graph throws an exception if you try to delete edges from a union-find graph.

## API

``    \$uf->add(@v)``

Add the vertices to the union-find.

union
``    \$uf->union([\$u, \$v], [\$w, \$x], ...)``

Add the edge u-v to the union-find. Also implicitly adds the vertices.

find
``    @partitions = \$uf->find(@v)``

For each given vertex, return the union-find partition it belongs to, or `undef` if it has not been added.

new
``    \$uf = Graph::UnionFind->new()``

The constructor.

same
``    \$uf->same(\$u, \$v)``

Return true of the vertices belong to the same union-find partition the vertex v belongs to, false otherwise.