Death Gun

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
awaykened
Problem type

Death Gun is wreaking havoc in the world of SAO::J, and must be stopped! As the protagonist, it is your duty to hunt him down and prevent any more innocent gamers from being logged off! However, Death Gun is adept at hiding and has disguised himself as one of the users in the judge! You know that Death Gun, whoever he/she is, has an extensive information network, and some certain people may know their identity. You have obtained this information network from the admins of SAO::J, in the form of a list with M items. Each item on the list is actually just a relation between user a and b. If you go to ask a who Death Gun is, he/she will simply redirect you to user b and then ask you to see them again; unless, you've already visited b in which case they will gladly tell you their information. To save time, you would like to find out an order to visit all the users on your list so that you do not waste time being redirected. If there are multiple ways to do so, output the people who appear on the list before those that appear later. If you think you will be going in a loop at any point in your list, you should avoid that group of people altogether, as they may be trolls (don't output their names)! Also, if there is someone that tells you to visit someone that you won't visit due to loops, (or someone who is someone who wants you to visit someone that you don't want to visit due to loops, or etc.), don't visit them.

Note: A person may have several different people they want you to visit first.

Input Specification

Line 1: 1 integer M, the number of items on your list (1 \le M \le 900)

Next M lines: 2 strings (with no spaces), space separated - A and B

Output Specification

On each line i, output the name of the ith person you should visit on your list.

Sample Input

3
Fataleagle Quantum
Quantum Xyene
Xyene DefinitelyNotDeathGun

Sample Output

DefinitelyNotDeathGun
Xyene
Quantum
Fataleagle

Explanation for Sample

If you go to Fataleagle, he will redirect you to Quantum, who will redirect you to Xyene, who will redirect you to DefinitelyNotDeathGun. Therefore you should visit DefinitelyNotDeathGun first, then Xyene since you've already visited DefinitelyNotDeathGun, Quantum since you've visited Xyene, and then Fataleagle since you've visited Quantum.

Comments


  • 3
    John  commented on March 25, 2022, 6:57 p.m.

    I guess Kirito was too busy fighting Death Gun to write this problem


  • 1
    Evang  commented on Nov. 26, 2020, 9:30 p.m.

    You should print everyone's names except for the people that are part of a loop.

    I took a long time to figure this out.


  • 10
    YouZ  commented on Dec. 8, 2015, 2:50 a.m.

    Lol I know a bunch of the people you used for test cases. They go to my school


  • 1
    bobhob314  commented on Nov. 3, 2015, 2:12 a.m.

    This was especially confusing to understand. Could anyone help me out? (or someone who is someone who wants you to visit someone that you don't want to visit due to loops, or etc.)


    • 0
      awaykened  commented on Nov. 3, 2015, 4:05 a.m.

      edges are not bidirectional, don't output cycles :)


  • 0
    bobhob314  commented on Nov. 3, 2015, 2:07 a.m.

    Hey all,

    I was hoping for some clarification on this.

    Also, if there is someone that tells you to visit someone that you won't visit due to loops, (or someone who is someone who wants you to visit someone that you don't want to visit due to loops, or etc.), don't visit them.

    Is this trying to say that all people in a connected component with a cycle should be avoided? Or is it that if the edges were all bidirectional, all people in a connected component that has a cycle should be avoided?

    So if we have

    3

    1 2

    2 1

    1 3

    Should we avoid 3?

    And if we have

    3

    1 2

    2 1

    3 1

    Should we avoid 3?


  • 3
    du1997du  commented on April 1, 2015, 5:11 a.m.

    Is it possible for one user to redirect to multiple users?