-
Source: ACM programming contest
- You are given a number of teams and the results of games played by pairs of these teams. The teams could be football teams, hockey teams, or whatever. Each team wil be identified by a single upper case letter. The maximum number of teams is therefore 26. Here is an example of an input file PROG1.DAT:
- A B
- C D
- A D
- C B
- D B
- C A
- Each line contains two uppercasse letters, separated by one blank space.
- The two letters on a line indicate the winner and loser (in that order) of a game played by those two teams. For example, the first line above indicates that A beat B.
- Once two teams have played a game, the winner of that game is ranked higher than the loser. Your mission is to rank the teams to produce a lineaar ordered list starting with the best team and progressing down to the worst one.
- The output will list all of the teams on one line, labelled and formatted as shown below. Each team will appeaar in the list only once, and there will be a blank between adjacent letters.
- If "X Y" occurs in the input then X will occur somewhere before Y in the output. There may be additional teams in between X and Y.
In the above example, team C was the only undefeated team, team A was defeated only by team C, and team D was defeated by yeam C (and possibly some other teams who defeated team D). Therefore, the output written by your program to the file PROG1.OUT would be:
Ranking of teams:
C A D B
-
You may assume that, for any given input, there will be a unique ordering (with no ties) of the teams.
In the above example, every team played every other team. That may not, however, be the case, as shown by the examples below:
|
Example 2:
|
|
- Example 3:
|
- B A
- A D
- B C
- C D
- B E
- E D
- A C
- C E
|
|
- X L
- Y K
- X K
- K L
- U W
- W X
- B X
- U Y
- B Y
X Y
- B U
|
- Ranking of teams:
- B A C E D
|
|
- Ranking of teams:
- B U W X Y K L
|
