Implement Union-Find and track components

Implement a Disjoint Set Union (Union-Find) data structure with union by rank and path compression. Design the API to support union(a, b), connected(a, b), and count() for the number of connected components. Given n nodes (0..n-

1. and a stream of operations, return the result of each connected query and the component count after each union. Analyze time and space complexity and discuss thread-safety considerations.

Implement Union-Find and Track Components

Implement a Disjoint Set Union (Union-Find) data structure supporting union(a, b), connected(a, b), and a running component count over n nodes labeled 0..n-1.

You are given n and a list of operations. Each operation is a list:

• ["union", a, b] — merge the sets containing a and b. After processing, append the current number of connected components to the result list.
• ["connected", a, b] — append true if a and b are in the same set, else false.

Return the list of results, one entry per operation, in order.

Use union by rank and path compression so each operation runs in near-constant amortized time.

Example:

n = 5
operations = [["union",0,1], ["union",2,3], ["connected",0,1], ["connected",0,2], ["union",1,3], ["connected",0,3], ["connected",0,4]]
result = [4, 3, true, false, 2, true, false]

After unioning 0-1 there are 4 components; after 2-3 there are 3; 0 and 1 are connected (true); 0 and 2 are not (false); unioning 1-3 merges the {0,1} and {2,3} sets leaving 2 components; now 0 and 3 are connected (true); node 4 is still isolated so 0-4 is false.

Constraints

• 1 <= n <= 10^5
• 0 <= a, b < n
• 0 <= number of operations <= 10^5
• Each operation type is either "union" or "connected"
• Self-operations are allowed (e.g. connected(x, x) is always true; union(x, x) is a no-op that leaves the count unchanged)

Hints

1. Maintain a parent array where parent[i] points toward the representative (root) of i's set. Initialize parent[i] = i so every node starts in its own component.
2. find(x) walks to the root. Apply path compression by repointing every node on the path directly to the root, which flattens the tree for future queries.
3. Use union by rank: attach the shorter tree under the taller one, and only increment rank when two equal-rank roots merge. Decrement the component count only when the two roots actually differ.
4. connected(a, b) is simply find(a) == find(b). For thread-safety in a concurrent setting you'd guard find/union with a lock or use a lock-free CAS-based union, since path compression mutates shared state.