YouTipUnion Find Quick Merge
## Union-Find Quick Merge
For a set of data, Union-Find mainly supports two operations:
* union(p,q) - Connect two elements p and q together.
* find(p) - Query which set element p belongs to.
* isConnected(p,q) - Check whether two elements p and q are connected together.
In the previous section, we used an **id** array to represent the Union-Find. In actual operations, the time complexity of finding is **O(1)**, but the connection efficiency is not high.
In this section, we will implement Union-Find in another way. Treat each element as a node that points to its parent node, and the root node points to itself. As shown in the figure below, node 3 points to node 2, indicating that 3 and 2 are connected together. Node 2 itself is the root node, so it points to itself.
!(#)
We also use an array to represent Union-Find, but the following group of elements uses **parent** to indicate the parent node that the current element points to. Each element points to itself and is independent.
!(#)
!(#)
If we perform union(4,3) at this time, make element 4 point to element 3:
!(#)
The array also changes accordingly:
!(#)
To determine whether two elements are connected, we only need to check whether their root nodes are the same.
As shown in the figure below, the root node of node 4 and node 9 are both 8, so they are connected.
!(#)
To connect two elements, we only need to find their corresponding root nodes and connect the root nodes together, then they are connected nodes.
Assuming we want to connect 6 and 4 in the figure above, we only need to make the root node 5 of 6 point to the root node 8 of 4.
!(#)
To construct this tree structure that points to parent nodes, use an array to build a tree that points to parent nodes. parent represents the parent node that element i points to.
...
private int[] parent;
private int count;// number of data elements
...
Find process, find the set number that element p belongs to, continuously query its parent node until reaching the root node. The characteristic of the root node is parent == p, with O(h) complexity, where h is the height of the tree.
...
private int find(int p){
assert( p >=0&& p < count );
while( p != parent)
p = parent;
return p;
}
...
Merge the sets that element p and element q belong to. Find the root nodes of both elements separately, and make one root node point to the other root node to merge the two sets. This operation has O(h) time complexity, where h is the height of the tree.
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
parent= qRoot;
}
### Java Example Code
**Source Package Download:*## UnionFind2.java File Code:
package tutorial.union;
/**
* Second version of unionFind
*/
public class UnionFind2 {
// Our second version of Union-Find, using an array to build a tree that points to parent nodes
// parent represents the parent node that the first element points to
private int[] parent;
private int count;// number of data elements
// Constructor
public UnionFind2(int count){
parent =new int;
this.count= count;
// Initialize, each parent points to itself, indicating each element forms its own set
for(int i =0; i =0&& p < count );
// Continuously query parent nodes until reaching the root node
// Characteristic of root node: parent == p
while( p != parent)
p = parent;
return p;
}
// Check whether element p and element q belong to the same set
// O(h) complexity, h is the height of the tree
public boolean isConnected(int p , int q ){
return find(p)== find(q);
}
// Merge the sets that element p and element q belong to
// O(h) complexity, h is the height of the tree
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
parent= qRoot;
}
}