Friend Groups That Merge and Get Queried
Implement processOps
Some people start out alone, and friendships then merge groups over time. You receive a list of operations: "merge the groups of a and b", or "are a and b in the same group?". Answer every operation in order: merges report the number of groups that remain, questions report 1 or 0.
A disjoint set (union-find) stores the groups as trees. Union by rank keeps the trees shallow by always hooking the shallower tree under the deeper one, and path compression flattens paths while searching.
Example 1:
Input: n = 6, ops = [[1,0,1],[1,2,3],[2,0,1],[1,1,3],[2,0,2],[2,0,4],[1,4,5]]
Output: [5,4,1,3,1,0,2]
Example 2:
Input: n = 3, ops = [[1,0,0],[2,1,2]]
Output: [3,0]
Example 3:
Input: n = 1, ops = [[2,0,0]]
Output: [1]
+ 13 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 10 people numbered 0 … n-1; at the start every person is alone in their own group - ●
ops is a list of at most 12 operations, each a row [kind, a, b] with 0 ≤ a, b < n: kind 1 means "merge the groups of a and b" (nothing happens if they are already the same group), kind 2 means "ask whether a and b are in the same group" - ●
The operations are processed in the given order and every operation produces one answer - ●
Return the answers: for a merge (kind 1) the number of groups that exist AFTER it, for a question (kind 2) 1 if a and b are in the same group and 0 otherwise
n =
ops =