Graph game

Two players play a game in a directed acyclic graph with the nodes $1,2,\dots,n$.

The game has a single shared token, which is initially in the node $x$. The players take turns to move the token along a single edge.

The game continues until one of the players has no moves left, because the current node has no edges to other nodes. Then the other player is the winner.

In a file graphgame.py, implement the class GraphGame with the following methods:

• add_link adds an edge from the node $a$ to the node $b$
• winning reports if the first player to move wins, when the token is initially in the node $x$ and both players make optimal moves

Implement the method winning efficiently using dynamic programming.

class GraphGame:
    def __init__(self, n):
        # TODO

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

    def winning(self, x):
        # TODO

if __name__ == "__main__":
    game = GraphGame(6)

    game.add_link(3, 4)
    game.add_link(1, 4)
    game.add_link(4, 5)

    print(game.winning(3)) # False
    print(game.winning(1)) # False

    game.add_link(3, 1)
    game.add_link(4, 6)
    game.add_link(6, 5)

    print(game.winning(3)) # True
    print(game.winning(1)) # False
    print(game.winning(2)) # False