Union Find

Union-Find

Question 1. Social network connectivity.

For the solution, union-find with path compression and a counter are used, which is initialized with a value equal to the number of members of the social network. The counter is decremented after each merge. When all the elements are combined, the counter will have a value of 1.

Question 2. Union-find with specific canonical element.

The solution is weighted union-find with path compression and an array of the same size that contains the values of the maximum element. This value is assigned with path compression and union.

Question 3. Successor with delete.

For the solution, union-find with path compression is used. When an element is deleted, it is combined with the next one (which, when the root of the given element is found, will give us a successor).