Verkkopeli

Kaksi pelaajaa pelaavat peliä suunnatussa syklittömässä verkossa. Pelissä on yksi yhteinen pelinappula, joka on alussa solmussa x. Pelaajat siirtävät nappulaa vuorotellen johonkin solmuun, johon pääsee suoraan kaarella nykyisestä solmusta.

Peli jatkuu, kunnes vuorossa oleva pelaaja ei voi tehdä mitään siirtoa eli pelinappula on solmussa, josta ei pääse mihinkään toiseen solmuun kaarta pitkin. Tällöin toinen pelaaja voittaa pelin.

Tehtäväsi on toteuttaa luokka GraphGame, jossa on seuraavat metodit:

• add_link lisää kaaren solmusta a solmuun b
• winning kertoo, voittaako aloittaja pelin solmusta x, kun molemmat pelaajat pelaavat optimaalisesti

Metodi winning tulee toteuttaa tehokkaasti dynaamisen ohjelmoinnin avulla.

Toteuta luokka tiedostoon graphgame.py seuraavan esimerkin mukaisesti.

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