Graph game

Consider a two player game in a directed acyclic graph (DAG). Initially the token is in a given vertex, and then the players take turns to move the token along a single directed edge. The game continues until one of the players has no moves left; that player is the loser and the other player is the winner.

Your task is to design a class that supports adding edges to the graph and finding if the starting player wins the game when the token is initially in a vertex x and both players make optimal moves.

You may assume that the number of vertices is at most 50 and that the methods of the class are called at most 200 times.

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

• constructor with the number of vertices as a parameter
• add_link adds an edge from a vertex a to a vertex b
• winning reports if the starting player wins the game when starting from a vertex x

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

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

    def winning(self,x):
        # TODO

if __name__ == "__main__":
    g = GraphGame(6)
    g.add_link(3,4)
    g.add_link(1,4)
    g.add_link(4,5)
    print(g.winning(3)) # False
    print(g.winning(1)) # False
    g.add_link(3,1)
    g.add_link(4,6)
    g.add_link(6,5)
    print(g.winning(3)) # True
    print(g.winning(1)) # False
    print(g.winning(2)) # False