Suuntaamattomassa verkossa on $n$ solmua. Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään kaaren verkkoon sekä laskemaan, mikä on pienin määrä kaaria, jotka tulisi lisätä, jotta verkko on yhtenäinen.

Voit olettaa, että $n$ on enintään $50$ ja luokan metodeita kutsutaan enintään $100$ kertaa.

Python

Toteuta tiedostoon connectivity.py luokka Connectivity, jossa on seuraavat metodit:

• konstruktori, jolle annetaan solmujen määrä
• add_edge lisää kaaren kahden solmun välille
• count ilmoittaa pienimmän määrän lisättäviä kaaria

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

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

    def count(self):
        # TODO

if __name__ == "__main__":
    c = Connectivity(5)
    print(c.count()) # 4
    c.add_edge(2,4)
    c.add_edge(3,5)
    print(c.count()) # 2
    c.add_edge(2,3)
    c.add_edge(3,4)
    print(c.count()) # 1
    c.add_edge(1,2)
    print(c.count()) # 0

Java

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

• konstruktori, jolle annetaan solmujen määrä
• addLink lisää kaaren kahden solmun välille
• count ilmoittaa pienimmän määrän lisättäviä kaaria

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

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

    public int count() {
        // TODO
    }

    public static void main(String[] args) {
        Connectivity c = new Connectivity(5);
        System.out.println(c.count()); // 4
        c.addEdge(2,4);
        c.addEdge(3,5);
        System.out.println(c.count()); // 2
        c.addEdge(2,3);
        c.addEdge(3,4);
        System.out.println(c.count()); // 1
        c.addEdge(1,2);
        System.out.println(c.count()); // 0
    }
}