Author: Musfiqur Sanim
Disjoint set union.
In a social network people can make friend by two types. When two people become friends, check whether it is possible by Type 1 method. If yes, then report “Found in friend list” otherwise report “Found by random”.
We will be using a Disjoin Set Data Structure that supports the following operations
Parent(N), get the id of the disjoint set to which A belongs.
isUnion(A,B), return is A and B in same set or not.
makeUnion(A,B), merge the two disjoint sets in which A and B belong respectively.
For each A,B if isUnion(A,B) is true then type1 otherwise type2 and call makeUnion(A,B) to marge them.
Author’s solution can be found here.