CSES - Turistikierros

Bittimaassa on n turistikohdetta, joiden välillä on yksisuuntaisia bussiyhteyksiä. Tehtäväsi on selvittää, onko olemassa tapaa aloittaa jostain kohteesta ja käydä läpi kaikki kohteet yhteyksien avulla. Samassa kohteessa saa vierailla useamman kerran.

Voit olettaa, että turistikohteita on enintään 50 ja luokan metodeita kutsutaan enintään 200 kertaa.

Python

Toteuta tiedostoon allplaces.py luokka AllPlaces, jossa on seuraavat metodit:

  • konstruktori, jolle annetaan turistikohteiden määrä
  • add_route lisää yhteyden kohteesta a kohteeseen b
  • check tutkii, onko turistikierrosta olemassa
class AllPlaces:
    def __init__(self,n):
        # TODO

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

    def check(self):
        # TODO

if __name__ == "__main__":
    a = AllPlaces(5)
    a.add_route(1,2)
    a.add_route(1,3)
    a.add_route(2,3)
    a.add_route(2,4)
    print(a.check()) # False
    a.add_route(2,5)
    print(a.check()) # False
    a.add_route(3,1)
    print(a.check()) # False
    a.add_route(5,4)
    print(a.check()) # True

Java

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

  • konstruktori, jolle annetaan turistikohteiden määrä
  • addRoute lisää yhteyden kohteesta a kohteeseen b
  • check tutkii, onko turistikierrosta olemassa
public class AllPlaces {
    public AllPlaces(int n) {
        // TODO
    }

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

    public boolean check() {
        // TODO
    }

    public static void main(String[] args) {
        AllPlaces a = new AllPlaces(5);
        a.addRoute(1,2);
        a.addRoute(1,3);
        a.addRoute(2,3);
        a.addRoute(2,4);
        System.out.println(a.check()); // false
        a.addRoute(2,5);
        System.out.println(a.check()); // false
        a.addRoute(3,1);
        System.out.println(a.check()); // false
        a.addRoute(5,4);
        System.out.println(a.check()); // true
    }
}