Samat painot

Tehtäväsi on tutkia, onko annetun verkon jokaisella virittävällä puulla sama paino.

Voit olettaa, että solmuja on enintään $50$ ja luokan metodeita kutsutaan enintään $100$ kertaa. Jokaisen kaaren paino on kokonaisluku välillä $1 \dots 1000$.

Python

Toteuta tiedostoon sameweight.py luokka SameWeight, jossa on seuraavat metodit:

• konstruktori, jolle annetaan solmujen määrä
  
• add_edge lisää solmujen $a$ ja $b$ välille kaaren, jonka paino on $x$
  
• check ilmoittaa, onko verkon kaikilla virittävillä puilla sama paino (jos verkko ei ole yhtenäinen, haluttu vastaus on True)
  

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

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

    def check(self):
        # TODO

if __name__ == "__main__":
    s = SameWeight(4)
    s.add_edge(1,2,2)
    s.add_edge(1,3,3)
    print(s.check()) # True
    s.add_edge(1,4,3)
    print(s.check()) # True
    s.add_edge(3,4,3)
    print(s.check()) # True
    s.add_edge(2,4,1)
    print(s.check()) # False

Java

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

• konstruktori, jolle annetaan solmujen määrä
  
• addEdge lisää solmujen $a$ ja $b$ välille kaaren, jonka paino on $x$
  
• check ilmoittaa, onko verkon kaikilla virittävillä puilla sama paino (jos verkko ei ole yhtenäinen, haluttu vastaus on true)
  

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

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

    public boolean check() {
        // TODO
    }

    public static void main(String[] args) {
        SameWeight s = new SameWeight(4);
        s.addEdge(1,2,2);
        s.addEdge(1,3,3);
        System.out.println(s.check()); // true
        s.addEdge(1,4,3);
        System.out.println(s.check()); // true
        s.addEdge(3,4,3);
        System.out.println(s.check()); // true
        s.addEdge(2,4,1);
        System.out.println(s.check()); // false
    }
}