CSES - Komponentit

Bittimaassa on n kaupunkia, joiden välillä ei ole aluksi teitä. Kaksi kaupunkia kuuluvat samaan komponenttiin, jos niiden välillä pystyy kulkemaan teiden avulla.

Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään tien kahden kaupungin välille sekä laskemaan, montako komponenttia kaupungit muodostavat.

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

Python

Toteuta tiedostoon components.py luokka Components, jossa on seuraavat metodit:

  • konstruktori, jolle annetaan kaupunkien määrä
  • add_road lisää tien kahden kaupungin välille
  • count ilmoittaa komponenttien määrän
class Components:
    def __init__(self,n):
        # TODO

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

    def count(self):
        # TODO

if __name__ == "__main__":
    c = Components(5)
    print(c.count()) # 5
    c.add_road(1,2)
    c.add_road(1,3)
    print(c.count()) # 3
    c.add_road(2,3)
    print(c.count()) # 3
    c.add_road(4,5)
    print(c.count()) # 2

Java

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

  • konstruktori, jolle annetaan kaupunkien määrä
  • addRoad lisää tien kahden kaupungin välille
  • count ilmoittaa komponenttien määrän
public class Components {
    public Components(int n) {
        // TODO
    }

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

    public int count() {
        // TODO
    }

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