Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään kaaren suuntaamattomaan verkkoon sekä selvittämään, kuinka pitkä on pisin sellainen polku, jossa jokaisen solmun tunnus on suurempi kuin edellisen solmun tunnus.

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

Python

Toteuta tiedostoon longpath.py luokka LongPath, jossa on seuraavat metodit:

• konstruktori, jolle annetaan solmujen määrä
• add_edge lisää kaaren kahden solmun välille
• calculate antaa pisimmän polun pituuden

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

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

    def calculate(self):
        # TODO

if __name__ == "__main__":
    l = LongPath(4)
    l.add_edge(1,2)
    l.add_edge(1,3)
    l.add_edge(2,4)
    l.add_edge(3,4)
    print(l.calculate()) # 2
    l.add_edge(3,2)
    print(l.calculate()) # 3

Java

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

• konstruktori, jolle annetaan solmujen määrä
• addEdge lisää kaaren kahden solmun välille
• calculate antaa pisimmän polun pituuden

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

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

    public int calculate() {
        // TODO
    }

    public static void main(String[] args) {
        LongPath l = new LongPath(4);
        l.addEdge(1,2);
        l.addEdge(1,3);
        l.addEdge(2,4);
        l.addEdge(3,4);
        System.out.println(l.calculate()); // 2
        l.addEdge(3,2);
        System.out.println(l.calculate()); // 3
    }
}