Sane's Monthly Algorithms Challenge: November 2008
You are a computer scientist for a popular online game which hosts one-on-one chess games between players across the world. After each game, the username of both players is recorded in the website's database, along with the username of the player who won.
The website has statistics for the Wins and Losses of each player. However, these statistics are poor representations since the most active members can increase their win count by 'picking' on bad players with low win-loss ratios. Some also cheat by playing against their own alternate accounts.
To help reduce this problem, they want to add an intelligent stat to each user, which indicates how many players the user "can" beat, given the playing history of all players and the following logical rule:
Player ~A~ can beat Player ~B~ if and only if Player ~A~ and Player ~B~ have different usernames and:
- Player ~A~ has beat Player ~B~ or
- Player ~A~ has beat Player ~C~ and Player ~C~ can beat Player ~B~.
This statistic will hopefully provide an incentive for users to compete against better players, and to not repeatedly pick on the same person.
Your job is, given the database of playing history, generate the database containing this new statistical attribute for each player.
The first line contains an integer ~n~ ~(1 \le n \le 10\,000)~.
The next ~n~ lines each contain two alphanumeric names of lengths no longer than ~20~, separated by a space. This line indicates that the first user "has" beat the second user. Names are case sensitive. A player can never play against himself.
On the first line, output an integer ~k~ ~(2 \le k \le 20\,000)~, representing the number of distinct names mentioned in the input file.
For each of the next ~k~ lines to follow, output a name you have not yet mentioned in the output file, followed by the number of users he/she "can" beat (the order of the output file does not matter).
7 Jim Denise Noobie111 AwesumChessPlyr1337 Gerald AwesumChessPlyr1337 AwesumChessPlyr1337 Denise Denise 2GudAtChessLOL 2GudAtChessLOL AwesumChessPlyr1337 Jim Gerald
6 Jim 4 Gerald 3 Noobie111 3 Denise 2 2GudAtChessLOL 2 AwesumChessPlyr1337 2