### 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.