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