Implement Union-Find for connectivity

Implement a Disjoint Set Union (Union-Find) data structure with path compression and union by rank. Support operations: make_set, find(x), union(x, y), and connected(x, y). Then, given an undirected graph with n nodes labeled 1..n and a list of edges, process q online connectivity queries efficiently. Analyze time and space complexity, and discuss edge cases such as duplicate unions and isolated nodes.

Union-Find Connectivity Queries

Implement a Disjoint Set Union (Union-Find) data structure with path compression and union by rank, then use it to answer connectivity queries on an undirected graph.

You are given an integer n (nodes are labeled 1..n), a list of undirected edges where each edge [a, b] connects nodes a and b, and a list of queries where each query [x, y] asks whether nodes x and y are connected (i.e. reachable from one another through the edges).

First union all the edges, then answer each query in order. Return a list of booleans: true if x and y are in the same connected component, false otherwise.

Notes:

• Duplicate or reversed edges (e.g. [1, 2] and [2, 1]) must be handled gracefully and have no extra effect.
• A node is always connected to itself, even if it is isolated (has no edges).
• Use path compression in find and union by rank in union so the amortized cost per operation is nearly O(1).

Example:

n = 6
edges = [[1, 2], [2, 3], [4, 5]]
queries = [[1, 3], [1, 4], [4, 5], [5, 6]]
returns [true, false, true, false]

Nodes {1,2,3} form one component and {4,5} form another; node 6 is isolated.

Constraints

• 1 <= n <= 10^5
• 0 <= number of edges <= 2 * 10^5
• 0 <= number of queries <= 2 * 10^5
• 1 <= a, b, x, y <= n
• Edges are undirected; duplicate and reversed edges may appear.

Hints

1. Maintain a parent array where each node initially points to itself; the root of a tree identifies its component.
2. In find, follow parent pointers to the root, then re-point every node on the path directly to the root (path compression).
3. In union, attach the shorter tree under the taller one using a rank array to keep trees shallow.
4. Two nodes are connected exactly when find(x) == find(y). A node is always its own root, so self-queries on isolated nodes return true.