How Big Is Your Friend Group
Implement groupSizes
People start out alone, and friendships merge groups. You receive a list of operations: "merge the groups of a and b", or "how big is the group of a?". Answer every operation in order with the size of the group of a (after the merge, for merge operations).
A disjoint set (union-find) stores the group sizes at the roots of trees. Union by size hooks the smaller tree under the larger one, which keeps the trees shallow.
Example 1:
Input: n = 6, ops = [[1,0,1],[1,2,3],[2,3,0],[1,1,3],[2,2,0],[1,4,5],[2,4,0],[1,0,5]]
Output: [2,2,2,4,4,2,2,6]
Example 2:
Input: n = 3, ops = [[1,1,1],[2,2,0]]
Output: [1,1]
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 changes if they are already together), kind 2 means "ask for the size of the group of a" (b is ignored) - ●
The operations are processed in the given order and every operation produces one answer - ●
Return the answers: for a question the size of the group of a; for a merge the size of the group of a AFTER the merge
n =
6
ops =
[[1,0,1], [1,2,3], [2,3,0], [1,1,3], [2,2,0], [1,4,5], [2,4,0], [1,0,5]]