AUSF-Editorial

PROBLEM LINK:

Contest

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.

1 Like