Tarkastellaan kahden pelaajan peliä suunnatussa syklittömässä verkossa. Alussa pelinappula on tietyssä solmussa, ja pelaajat siirtävät vuorotellen nappulan johonkin solmuun, johon pääsee suoraan kaarella nykyisestä solmusta. Peli jatkuu, kunnes pelaaja ei voi tehdä mitään siirtoa, jolloin hän häviää pelin ja toinen pelaaja voittaa.

Tehtäväsi on toteuttaa luokka, jonka avulla voi lisätä kaaria verkkoon ja selvittää, onko aloittavan pelaajan mahdollista voittaa peli, jos aloitussolmu on x ja molemmat pelaajat pelaavat optimaalisesti.

Voit olettaa, että solmuja on enintään 50 ja luokan metodeita kutsutaan enintään 200 kertaa.

Python

Toteuta tiedostoon graphgame.py luokka GraphGame, jossa on seuraavat metodit:

• konstruktori, jolle annetaan solmujen määrä
• add_link lisää kaaren solmusta a solmuun b
• winning kertoo, voittaako aloittaja pelin solmusta 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

Java

Toteuta tiedostoon GraphGame.java luokka GraphGame, jossa on seuraavat metodit:

• konstruktori, jolle annetaan solmujen määrä
• addLink lisää kaaren solmusta a solmuun b
• winning kertoo, voittaako aloittaja pelin solmusta x

public class GraphGame {
    public GraphGame(int n) {
        // TODO
    }

    public void addLink(int a, int b) {
        // TODO
    }

    public boolean winning(int x) {
        // TODO
    }

    public static void main(String[] args) {
        GraphGame g = new GraphGame(6);
        g.addLink(3,4);
        g.addLink(1,4);
        g.addLink(4,5);
        System.out.println(g.winning(3)); // false
        System.out.println(g.winning(1)); // false
        g.addLink(3,1);
        g.addLink(4,6);
        g.addLink(6,5);
        System.out.println(g.winning(3)); // true
        System.out.println(g.winning(1)); // false
        System.out.println(g.winning(2)); // false
    }
}