Tehtäväsi on tutkia, onko verkon pienin virittävä puu yksikäsitteinen eli on tarkalleen yksi tapa muodostaa virittävä puu, jonka paino on pienin.

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 uniquetree.py luokka UniqueTree, 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 pienin virittävä puu yksikäsitteinen (jos verkko ei ole yhtenäinen, haluttu vastaus on False)

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

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

    def check(self):
        # TODO

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

Java

Toteuta tiedostoon UniqueTree.java luokka UniqueTree, 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 pienin virittävä puu yksikäsitteinen (jos verkko ei ole yhtenäinen, haluttu vastaus on false)

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

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

    public boolean check() {
        // TODO
    }

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