PROBLEM LINK:
Author: Musfiqur Sanim
DIFFICULTY:
MEDIUM.
PREREQUISITES:
Disjoint set union.
PROBLEM:
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”.
QUICK EXPLANATION:
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 SOLUTIONS:
Author’s solution can be found here.