Basics of Union-Find

I. Concept and Introduction

The Union-Find data structure is a tree-like structure used to handle the merging and querying of disjoint sets.

The idea of Union-Find is to represent the entire forest with an array (parent), where the root node of a tree uniquely identifies a set. By finding the root of a given element, we can determine which set it belongs to.

II. Applicability

Union-Find is used in problems involving a set of N elements. Initially, each element forms a single-element set, and then sets containing elements of the same group are merged in a certain order, while repeatedly checking which set an element belongs to. Although this process seems straightforward, it deals with extremely large datasets. Other data structures would require excessive space and time, making Union-Find the only viable solution.

III. Basic Data Representation of Union-Find

As shown in the figure, elements 0, 2, 4, 6, 8 all belong to the set 0, indicating that these five elements are connected. Similarly, elements 1, 3, 5, 7, 9 all belong to the set 1, indicating that these five elements are connected.

To construct a class UnionFind, initialize each id[i] to point to itself, with no elements merged:

...
public UnionFind1(int n) {
    count = n;
    id = new int[n];
    // Initialization, each id[i] points to itself, no elements merged
    for (int i = 0; i < n; i++)
        id[i] = i;
}
...

Java Example Code

Source Code Download: Download

UnionFind.java File Code:

package tutorialpro.union;

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;
    }
}