[liga]

Zagadka:
W mieście żyje n mieszkańców. Wsród nich jest burmistrz. Burmistrz nie zna nikogo, ale wszyscy znają burmistrza. Możemy się pytać czy osoba i zna osobę j. Problem: znajdź burmistrza w jak najmniejszej ilości zapytań.
#matematyka #programowanie #algorytmy

[Zelman666]

@liga: Każdy zna burmistrza... pytasz kogokolwiek i albo to burmistrz albo ta osoba zna burmistrza, więc jednym pytaniem go znajdziesz.

[m.....u]

@Zelman666: No ale pytasz np mnie i ja Ci mówię, że osoba na którą wskazujesz nie jest burmistrzem...

[Filem00n]

@mraauuu: ale w zadaniu nie uwzględniono śmieszkowania( ͡° ͜ʖ ͡°)

[s.....k]

@Zelman666:

Możemy się pytać czy osoba i zna osobę j.

[m.....u]

@liga: A czy osoby które nie są burmistrzem znają kogoś poza burmistrzem?

[liga]

@mraauuu: losowo mogą znać się różne osoby w mieście.
@Golob: wygrywasz litr kompotu! możesz zonaczyć odpowiedź jako spoiler :)

[Golob]

@liga: już nie mogę. przerzucam poniżej.

[ponton]

@liga: Robisz BFS-a/DFS-a po skierowanym grafie znajomości (zaczynając od dowolnej osoby), aż znajdziesz liść, czyli wierzchołek bez krawędzi wychodzących. On jest burmistrzem, bo burmistrz nie zna nikogo, a każdy inny zna przynajmniej jedną osobę (burmistrza).

[liga]

@ponton: takie podejście miałem też na początku, ale mnie opieprzono, że to strzelanie do komara z armaty tzn. budowanie grafu, implementacja rozwiązania itd. Rozwiązanie Goloba jest moim zdaniem najlepsze dzięki prostocie implementacji :)

[GwnBrz]

@liga: Zdaje się, że @ponton zaproponował dokładnie to samo, tyle że opisał rozwiązanie pojęciami z grafów. Wiesz, implementacja DFSa nie musi wiązać się z pisaniem klasy Node, można to zrobić na jednym wektorze :-).

[liga]

@GwnBrz: po krótkim przemyśleniu zgadzam sie ;)