CSES - Planets

The game has n planets numbered 1,2,\dots,n. A player starts at the planet 1 and wins the game by reaching the planet n.

The planets are connected by teleports. Each teleport is described by a pair (a,b), where a<b, and teleports a player from the planet a to the planet b.

You have successfully played the game through, but you want to prevent anyone else from winning the game. How many teleports do you need to remove from the game?

In a file planets.py, implement the class Planets with the following methods:

  • add_teleport adds a teleport from the planet a to the planet b
  • min_removals returns the minimum number of teleports to remove
class Planets:
    def __init__(self, n):
        # TODO

    def add_teleport(self, a, b):
        # TODO

    def min_removals(self):
        # TODO

if __name__ == "__main__":
    planets = Planets(5)

    print(planets.min_removals()) # 0

    planets.add_teleport(1, 2)
    planets.add_teleport(2, 5)
    print(planets.min_removals()) # 1

    planets.add_teleport(1, 5)
    print(planets.min_removals()) # 2