AIOC Banner

Problem: Friendlist

Want to try solving this problem? You can submit your code online if you log in or register.

The problems in this set are designed to be more accessible to beginning coders. As a learning aid, walkthroughs discussing how to solve the problems in this set are available by clicking on this link. On completion of this problem set, students should have experience at using arrays to store, search through, and manipulate large data sets.


Input File: listin.txt
Output File: listout.txt
Time Limit: 1 second
Memory Limit: 64MB

The face of electronic gaming has changed dramatically over the past few decades. Forget text adventure games and rickety Asteroids cabinets - these days it's all about ultra-realistic graphics, motion-sensing wands and high-end CPUs. But despite all this, simple games with basic rules and crisp art are doing as well as ever. One such game is Friendlist, a multiplayer game requiring nothing more than an internet browser to play.

In Friendlist, players add each other as 'friends' based on looks, reputation, or even real life connections. (Friendship is mutual: if Alice has Bob as a friend, then Bob has Alice as a friend too. Of course, people cannot be friends with themselves.) As the game progresses, dedicated players can grind their way through quiz-like minigames in order to impress their peers. However, adding 'friends' to one's friendlist remains the cornerstone of the game. The bigger the friendlist, the better the player.

The object of the game is to have the biggest friendlist (that is, the most friends). Your task here is to take a list of Friendlist friendships and determine the winner. There may be more than one person tied for first place: if so, your program should list them all.


The first line of input will contain the integer f, 1 <= f <= 1,000,000.

Each of the following f lines will be of the form a b, where a and b are different player IDs. This indicates that player #a is friends with player #b, and vice versa. All player IDs are integers between 0 and 1000 inclusive.

(Note that no friendship will ever be listed twice: for example, if "2 5" is one of the lines in the input, then neither "2 5" nor "5 2" will appear anywhere else in the input.)


Output should consist of all the player IDs that are tied for biggest friendlist. These IDs should be given in ascending order.

Sample Input 1

5 6
0 1
1 4
5 4
1 2
4 0

Sample Output 1



The input above describes the following set of friendships:

Player IDFriendlist
01, 4
10, 2, 4
40, 1, 5
54, 6

Players 1 and 4 are tied for biggest friendlist.

Sample Input 2

123 456
456 789
100 200

Sample Output 2



In this case, player 456 clearly has the biggest friendlist (two friends).


The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2018

Page generated: 24 April 2018,  7:17am AEST