Union-Find Quick Find
This section introduces the basic operations based on the disjoint-set union structure from the previous section: query, union, and determining whether elements are connected.
Query the set ID of an element and return it directly.idArray value,O(1)time complexity.
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
Merge elementspand elementqThe set it belongs to. The union process requires traversing all elements, then merging the set IDs of the two elements. This process is...O(n)Complexity.
...
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[i] == pID)
id[i] = qID;
}
...
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[i] == pID)
id[i] = qID;
}
...
Java example code
Source package download:Download
UnionFind1.java file code:
package example.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[n];
// Initialize: each id[i] points to itself, no merged elements
for (int i = 0; i < n; i++)
id[i] = i;
}
// find process, find the set number corresponding to element p
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// check whether 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 merge process needs to traverse all elements once and merge the set IDs of the two elements
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}
/**
* 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[n];
// Initialize: each id[i] points to itself, no merged elements
for (int i = 0; i < n; i++)
id[i] = i;
}
// find process, find the set number corresponding to element p
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// check whether 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 merge process needs to traverse all elements once and merge the set IDs of the two elements
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}