On the right side of the Facebook News Feed (the page that loads by default when you log in), there is a section titled "People You May Know", which suggests various people that you may know in real life, but have not added as Friends. The actual logic used by Facebook to decide which names/profiles to display there is undoubtedly more complex, but we consider here a simple alternative (or possibly a simplified version) of the algorithm used.
Given a Friendship Graph, your task is to calculate the names that will show up under the "People You May Know" section of the Facebook News Feed for a given person.
The Friendship Graph will be specified in terms of pairs of friends. A number of such pairs will be given in order that the Graph be constructed.
Given this information, we calculate Friend Suggestions by using the following logic:
- Select all those people, who are NOT Friends with the person under consideration.
- For each person in this set, calculate the number of Mutual Friends with the person under consideration. Mutual Friends are people who are Friends of both parties involved.
- Discard all those who do NOT have any Mutual Friends with the person under consideration.
- The first line of the input will contain a single integer, T, which specifies that number of testcases that follow.
- Each test case consists of 3 lines:
- The 1st and the 2nd lines of each testcase consist of N names each (N not specified), such that the ith name in the first line is friends with the ith name in the second line.
- The 3rd line consists of an additional M (again, M not specifed) names, for each of which you need to calculate Friend Suggestions.
- Each name will be a single word, consisting of only lowercase alphanumeric or underscore characters, less than 50 characters in length.
- The total number of people for any one test case can be up to 1000.
- Corresponding to each name in the 3rd line of a testcase, output 1 line, which contains the Friend Suggestions for that person, which is nothing but a list of names, separated by spaces, in the order of decreasing mututal friends.
- If multiple suggested names have same number of mutual friends, output them in a Lexicographical Ordering.
- Leave a blank line between the outputs corresponding to the various testcases.
john mary mary anna adam luke john
adam adam john mary brad adam luke
ryan kyl3 kyl3
sean stan emma
Problem Setter: Kaustubh Karkare