Description
Read a list of friend relations A-B, A-D, C-A, C-D, ..., and determine friendship circles.2 Problem Statement These days, it seems that we expect computers to direct our social lives, even to the point of choosing our friends. Of course, as programmers, we get to implement these choice algorithms, as in this problem.
Given a \friend relation" { a set of pairs of people who designate each other as \friends"
{ and a particular person (C, \the client") your algorithm is to select any speci ed number
(N) of people who are not friends of C, but who are friends of friends of C. Speci cally, the algorithm picks those people who know the greatest numbers of C's friends. For example,
if N = 2, C is Jack, and the friend relation is
Jack/Mary Mary/Claire Jack/Tom Tom/Claire Jack/Richard
Tod/Richard Claire/Richard Jack/Jill Jill/June June/Tod
Jill/Tod Jill/Peter Mary/Tom Richard/Tom Jill/Tom
the program would select Claire (who knows Jack's friends Mary, Tom, and Richard) and Tod (who knows Richard and Jill). Jack's other friends of friends are June and Peter (who both know Jill). The relationships between Jack's friends (such as Mary and Tom) are irrelevant. Implicitly, Jack is his own friend, so that he is not in the list of suggestions. The \friend" relation is symmetric: you are my friend i (if and only if) I am yours.
The input will consist of multiple sets of data in free format. Each set begins with an
integer, N, and a name (consisting of a string of non-whitespace characters), C. There
then follows a sequence of an even number of names, each successive pair of which denotes a friend relationship. A given friend relationship will appear only one in the sequence (with either member rst). The implicit friendship of a person with himself will not be included.
The sequence terminates with two asterisks (separated by whitespace). For each input set, the output consists of a list of whitespace-separated names in alpha-betical order giving the N non-friends of C who are acquainted with the most friends of C. You may assume that there will always be at least N non-friends of C. In case too many people know the smallest qualifying number of friends, choose those that come earlier in
alphabetical order. Thus, if N = 2 and Mike knows two of C's friends while Sam, Jill, and
Mary know one, then choose Jill and Mike.
Example
Input:2 Jack
Mary Claire Jack Tom Tom Claire Jack Richard
Jack
Mary
Tod Richard Claire Richard Jack Jill Jill June June Tod
Jill Tod Jill Peter Mary Tom Richard Tom Jill Tom
* *
3 Jack
Mary Claire Jack Tom Tom Claire Jack Richard
Jack
Mary
Tod Richard Claire Richard Jack Jill Jill June June Tod
Jill Tod Jill Peter Mary Tom Richard Tom Jill Tom
* *
Output:
Claire Tod
Claire June Tod
Comments
Post a Comment