CSES - Kaupungit Bittimaassa on $n$ kaupunkia, joiden välillä ei ole vielä teitä. Tehtäväsi on toteuttaa luokka, jonka avulla pystyy lisäämään tien kahden kaupungin välille sekä tutkimaan, onko kahden kaupungin välillä reittiä.

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

Python

Toteuta tiedostoon cities.py luokka Cities, jossa on seuraavat metodit:
  • konstruktori, jolle annetaan kaupunkien määrä
  • add_road lisää tien kahden kaupungin välille
  • has_route tarkastaa, onko kahden kaupungin välillä reittiä
class Cities:
    def __init__(self,n):
        # TODO

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

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

if __name__ == "__main__":
    c = Cities(5)
    c.add_road(1,2)
    c.add_road(1,3)
    c.add_road(4,5)
    print(c.has_route(1,5)) # False
    c.add_road(3,4)
    print(c.has_route(1,5)) # True
Java

Toteuta tiedostoon Cities.java luokka Cities, jossa on seuraavat metodit:
  • konstruktori, jolle annetaan kaupunkien määrä
  • addRoad lisää tien kahden kaupungin välille
  • hasRoute tarkastaa, onko kahden kaupungin välillä reittiä
public class Cities {
    public Cities(int n) {
        // TODO
    }

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

    public boolean hasRoute(int a, int b) {
        // TODO
    }

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