Union-Find Basics
I. Concept and Introduction
Union-Find is a tree-shaped data structure used to handle the merging and querying of some disjoint sets.
The idea of Union-Find is to use an array to represent an entire forest (parent). The root node of a tree uniquely identifies a set; as long as we find the tree root of an element, we can determine which set it belongs to.
II. Applicability Notes
Union-find sets are used in someNIn set application problems with elements, we usually let each element form a singleton set at the beginning, then merge the sets containing elements of the same group in a certain order, and repeatedly find which set an element belongs to during the process. This process may seem simple, but when the amount of data is extremely large, if other data structures are used to describe it, the space required is often too large for the computer to bear, and the result cannot be computed in a short time. Therefore, only the union-find set can be used to handle it.
III. Basic Data Representation of Union-Find Set
Again as shown above0、2、4、6、8The following are all0This set represents0、2、4、6、8These five elements are connected,1、3、5、7、9The following are all1This set represents0，1、3、5、7、9These five elements are connected.
Construct a class UnionFind, initialize it so that each id[i] points to itself, with no merged elements:
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;
}
...
Java Example Code
Source code package download:Download
UnionFind.java file code:
public class UnionFind{
private int[] id;
// number of data elements
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
}