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.

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
    }
}