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