Union Find | Disjoint Set Union | Set Size

Prereq: Disjoint Set Union Review

For this problem we now ask you to do something similar to the introductory problem, but this time instead of checking whether or not 2 values belong to the same set, we want to know the size of the set that a value belongs to. Therefore, we now support a different set of 2 operations:

  1. merge(x, y) merge the sets that x and y belong to,
  2. count(x) returns the size of the set that x belongs to.


1merge(1, 2)
2merge(2, 3)
3count(3) => 3
4count(4) => 1

We merge elements 1 and 2 then we merge the set of 1 and 2 with the element 3, so we should have now have 2 sets, [1, 2, 3] and [4]. Therefore the set that 3 belongs to contains 3 elements, while the set that 4 belongs to contains 1 element.




Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3

Get premium for instant access to all content and solutions