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