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.

Toteuta luokka AllTrees, jossa on seuraavat metodit:

• add_edge lisää verkkoon kaaren
• count ilmoittaa virittävien puiden määrän

Verkko on suuntaamaton ja voit myös olettaa, että siinä ei ole kahta samanlaista kaarta.

Tässä tehtävässä riittää toteuttaa raa'an voiman ratkaisu. Sinun tulee käyttää menetelmää, jonka toiminnan ymmärrät itse (ei matriiseihin perustuvaa ratkaisua, jos et osaa todistaa sitä).

Toteuta luokka tiedostoon spanning.py seuraavan esimerkin mukaisesti.

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