YouTipUnion Find Quick
# Union-Find Quick Find
This section builds upon the Union-Find structure from the previous section to introduce basic operations: find, union, and checking connectivity.
To find the set ID of an element, directly return the value from the **id** array, with a time complexity of **O(1)**.
...
private int find(int p){
assert p >=0&& p < count;
return id;
}
...
To merge the sets containing element **p** and element **q**, the merging process requires iterating through all elements once, then merging the set IDs of the two elements. This process has a complexity of **O(n)**.
...
public void unionElements(int p, int q){
int pID = find(p);
int qID = find(q);
if(pID == qID)
return;
for(int i =0; i < count; i++)
if(id== pID)
id= qID;
}
...
### Java Example Code
**Source Code Package Download:**(#)
## UnionFind1.java File Code:
package .union;
/**
* First version of Union-Find
*/
public class UnionFind1 {
// Our first version of Union-Find is essentially an array
private int[] id;
// Number of data elements
private int count;
public UnionFind1(int n){
count = n;
id =new int;
// Initialize, each id points to itself, no merged elements
for(int i =0; i =0&& p < count;
return id;
}
// Check if element p and element q belong to the same set
// O(1) complexity
public boolean isConnected(int p, int q){
return find(p)== find(q);
}
// Merge the sets containing element p and element q
// O(n) complexity
public void unionElements(int p, int q){
int pID = find(p);
int qID = find(q);
if(pID == qID)
return;
// The merging process requires iterating through all elements once, merging the set IDs of the two elements
for(int i =0; i < count; i++)
if(id== pID)
id= qID;
}
}