Implementing the Union-Find Data Structure in JavaScript

The Union-Find (also known as Disjoint Set Union or DSU) data structure is a powerful tool for managing a collection of disjoint sets. It's particularly useful in algorithms involving connected components, such as Kruskal's algorithm for Minimum Spanning Trees or detecting cycles in a graph. Your task is to implement this efficient data structure in JavaScript.

Problem Description

You are tasked with creating a JavaScript class, UnionFind, that can manage a collection of elements partitioned into disjoint sets. The structure should support two primary operations:

1. union(element1, element2): Merges the set containing element1 with the set containing element2. If both elements are already in the same set, this operation does nothing.
2. find(element): Returns a representative (or root) of the set that element belongs to. This representative should be consistent for all elements within the same set.

To optimize performance, you should implement two key optimizations:

• Path Compression: During a find operation, flatten the structure of the tree by making every node on the path from the element to the root point directly to the root.
• Union by Rank (or Size): When merging two sets, attach the shorter tree (based on rank or size) to the root of the taller tree. This helps keep the trees relatively balanced, preventing degenerate cases.

The UnionFind class should be initialized with the number of elements it will manage. Elements will be represented by integers from 0 to n-1, where n is the initial number of elements.

Examples

Example 1:

Input:
n = 5 // Represents elements 0, 1, 2, 3, 4
operations = [
    { type: 'union', arg1: 0, arg2: 1 },
    { type: 'union', arg1: 2, arg2: 3 },
    { type: 'find', arg1: 1 },
    { type: 'find', arg1: 3 },
    { type: 'union', arg1: 1, arg2: 3 },
    { type: 'find', arg1: 0 },
    { type: 'find', arg1: 2 }
]

Output:
[1, 3, 1, 1] // Results from 'find' operations in order

Explanation:

1. Initialize UnionFind with 5 elements. Each element is in its own set: {0}, {1}, {2}, {3}, {4}.
2. union(0, 1): Merges sets containing 0 and 1. Sets are now: {0, 1}, {2}, {3}, {4}. (Let's say 0 becomes root)
3. union(2, 3): Merges sets containing 2 and 3. Sets are now: {0, 1}, {2, 3}, {4}. (Let's say 2 becomes root)
4. find(1): Returns the root of the set containing 1, which is 0.
5. find(3): Returns the root of the set containing 3, which is 2.
6. union(1, 3): Merges the set containing 1 (root 0) with the set containing 3 (root 2). Sets are now: {0, 1, 2, 3}, {4}. (Let's say 0 remains root and 2's parent becomes 0, or vice-versa depending on rank/size).
7. find(0): Returns the root of the set containing 0, which is 0.
8. find(2): Returns the root of the set containing 2. After path compression (if applied and 2's parent was not already root), it will point directly to 0. The output will be 0.

Example 2:

Input:
n = 3
operations = [
    { type: 'find', arg1: 0 },
    { type: 'union', arg1: 0, arg2: 1 },
    { type: 'find', arg1: 1 },
    { type: 'union', arg1: 1, arg2: 2 },
    { type: 'find', arg1: 0 },
    { type: 'find', arg1: 2 }
]

Output:
[0, 1, 0]

Explanation:

1. Initialize UnionFind with 3 elements. Sets: {0}, {1}, {2}.
2. find(0): Returns 0.
3. union(0, 1): Merges sets. Sets: {0, 1}, {2}. (Let's say 0 is root).
4. find(1): Returns 0.
5. union(1, 2): Merges the set containing 1 (root 0) with the set containing 2 (root 2). Sets: {0, 1, 2}. (Let's say 0 remains root, 2's parent becomes 0).
6. find(0): Returns 0.
7. find(2): Returns 0 (after potential path compression).

Example 3: (Edge Case - Already in the same set)

Input:
n = 4
operations = [
    { type: 'union', arg1: 0, arg2: 1 },
    { type: 'union', arg1: 2, arg2: 3 },
    { type: 'union', arg1: 0, arg2: 2 },
    { type: 'union', arg1: 1, arg2: 3 }, // Already in the same set
    { type: 'find', arg1: 0 },
    { type: 'find', arg1: 3 }
]

Output:
[root, root] // Example: [0, 0] if 0 is the final root

Explanation:

The operation union(1, 3) will be a no-op because elements 1 and 3 will already belong to the same set after the previous unions. The find operations will return the same representative for both 0 and 3.

Constraints

• 1 <= n <= 10^5: The number of elements the UnionFind structure will manage.
• The elements are integers from 0 to n-1.
• The operations array will contain at most 10^5 operations.
• Each operation in the operations array will be either { type: 'union', arg1: number, arg2: number } or { type: 'find', arg1: number }.
• 0 <= arg1, arg2 < n.
• The find and union operations should aim for near-constant time complexity on average (amortized $O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function, which grows extremely slowly and is practically constant for all realistic input sizes).

Notes

• You will need to decide how to store the parent of each element and, if using union by rank/size, how to store that information as well. An array is a common choice.
• Consider using a Map or an array to store the parent pointers and ranks/sizes. For elements 0 to n-1, an array is generally more efficient.
• The find operation is where path compression is applied.
• The union operation should call find to determine the roots of the sets to be merged.
• If union is called with elements already in the same set, it should not alter the structure.
• The find operation should always return the same representative for all elements in the same set.
• The choice between "union by rank" and "union by size" is up to you, but one of them must be implemented for optimization. Union by size is often simpler to implement.