Pisin polku

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.

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