Implement Union-Find for connectivity
Company: Motive
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: This question evaluates understanding and implementation of the Disjoint Set Union (Union-Find) data structure—including path compression and union by rank—and competency in processing online connectivity queries on undirected graphs, categorized under Coding & Algorithms in the graph algorithms and data structures domain.
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.
Examples
Input: (6, [[1, 2], [2, 3], [4, 5]], [[1, 3], [1, 4], [4, 5], [5, 6]])
Expected Output: [True, False, True, False]
Explanation: Components: {1,2,3}, {4,5}, {6}. 1-3 connected, 1-4 not, 4-5 connected, 5-6 not.
Input: (1, [], [[1, 1]])
Expected Output: [True]
Explanation: A single isolated node is always connected to itself.
Hints
- Maintain a parent array where each node initially points to itself; the root of a tree identifies its component.
- In find, follow parent pointers to the root, then re-point every node on the path directly to the root (path compression).
- In union, attach the shorter tree under the taller one using a rank array to keep trees shallow.
- 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.