Problem Statement

Implement a Disjoint Set Union (DSU), also known as Union-Find, data structure. This structure should efficiently manage a collection of disjoint sets and support operations to merge sets and query connectivity.

Requirements

• The DSU implementation must incorporate both union by rank and path compression optimizations.
• Design an API that includes the following methods:
  • union(a, b): Merges the sets containing elements a and b.
  • connected(a, b): Returns true if elements a and b are in the same set, false otherwise.
  • count(): Returns the total number of disjoint sets (connected components) currently in the structure.
• The system will be initialized with n nodes, indexed from 0 to n-1.
• Process a stream of operations (calls to union, connected, or count).

Deliverables

• For each connected(a, b) query, return its boolean result.
• For each union(a, b) operation, return the total number of connected components after the union has been performed.
• Provide a detailed analysis of the time and space complexity of your implementation.
• Discuss comprehensive thread-safety considerations for concurrent access to the DSU structure.

Constraints & Assumptions

• Nodes are integers in the range 0 to n-1.