CSES - Kaikki puut Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään kaaren verkkoon sekä laskemaan, montako erilaista virittävää puuta verkolle voidaan muodostaa.

Voit olettaa, että verkossa on enintään $5$ solmua ja siihen lisätään enintään $10$ kaarta. Jokainen kaari on suuntaamaton ja verkossa ei ole kahta samanlaista kaarta.

Python

Toteuta tiedostoon alltrees.py luokka AllTrees, jossa on seuraavat metodit:
  • konstruktori, jolle annetaan solmujen määrä
  • add_edge lisää verkkoon kaaren
  • count ilmoittaa virittävien puiden määrän
class AllTrees:
    def __init__(self,n):
        # TODO

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

    def count(self):
        # TODO

if __name__ == "__main__":
    a = AllTrees(3)
    a.add_edge(1,2)
    print(a.count()) # 0
    a.add_edge(1,3)
    print(a.count()) # 1
    a.add_edge(2,3)
    print(a.count()) # 3
Java

Toteuta tiedostoon AllTrees.java luokka AllTrees, jossa on seuraavat metodit:
  • konstruktori, jolle annetaan solmujen määrä
  • addEdge lisää verkkoon kaaren
  • count ilmoittaa virittävien puiden määrän
public class AllTrees {
    public AllTrees(int n) {
        // TODO
    }

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

    public int count() {
        // TODO
    }

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