Blokowanie dróg - szukanie algorytmu grafowego Opcje

[glogu]

Ponieważ nie ma działu algorytmy umieszczam tutaj. Have fun

W odległym państwie, pewna partia postanowiła w ramach antyrządowego protestu zablokować najważniejsze drogi w państwie. Przewodniczący partii p. XYZ wyznaczył wstępny plan, dróg, na których powinny powstać blokady, jak również mianował w każdym mieście przewodniczącego lokalnego oddziału partii. Każdy oddział lokalny miał czuwać nad stanem blokady wszystkich dróg wjazdowych/wyjazdowych z miasta.

XYZ ustalił również następujące zasady strajku: "Jeśli zadzwonię do któregoś z lokalnych przewodniczących, wtedy on będzie musiał <<puścić sygnał>> każdemu z szefów blokad, którzy kontrolują ruch na drodze łączącej miasto z sąsiednimi. Szef blokady, jeśli dostanie sygnał tylko od jednego przewodniczącego, zobowiązany będzie do zmiany stanu blokady - tzn. jeśli droga była zablokowana, ma ją odblokować; jeśli odblokowana - zablokować. Jeśli otrzyma dwa sygnały lub nie otrzyma sygnału wcale - ma pozostawać w gotowości, ale stanu drogi nie zmieniać."
XYZ objął osobiście przewodnictwo w stolicy - i ze względu na swoją pozycję, nie zamierza kontaktować się z działaczami terenowymi na drogach wlotowych do stolicy.

Czy XYZ jest w stanie zablokować cały kraj kontaktując się wyłącznie z lokalnymi przewodniczącymi partii? Jakie telefony musi XYZ wykonać (zgodnie z kolejnością w spisie kontaktów), aby wszystkie drogi w kraju zostały zablokowane ?

Żadna droga nie łączy miasta z samym sobą. Droga jest blokowana zawsze dla ruchu w obydwu kierunkach. Pomiędzy dwoma miastami może być tylko i wyłącznie jedna droga dojazdowa. Z każdego miasta można dojechać do dowolnego innego.

Czy ktoś ma pomysł jak to rozwiązać ? Albo chociaż kawałek pomysłu ? Albo spotkał się gdzieś z takim (lub podobnym) zadaniem i wie gdzie znaleźć rozwiązanie ? Z góry dziękuje za pomoc

Żadna droga nie łączy miasta z samym sobą. Droga jest blokowana zawsze dla ruchu w obydwu kierunkach. Pomiędzy dwoma miastami może być tylko i wyłącznie jedna droga dojazdowa. Z każdego miasta można dojechać do dowolnego innego.

[Zyx]

Ja bym zaczął od napisania, z jakiego konkursu programistycznego jest to zadanie. Google niestety coś słabo indeksuje takie rzeczy...

[glogu]

mamy takie cos zrobić w ramach studiów. Ponieważ nie posądzam naszych prowadzacych o wymyslenie calkowicie oryginalnego zadania więc mam nadzieje ze ktos sie moze z czymś podobnym zetknął kiedyś

[Kocurro]

Mam rozwiązanie i za niewielkim wsparciem (500 pln) funduszu rozwijania pijaństwa wśród studentów jestem w stanie podzielić się rozwiązaniem. Jeśli nie chcesz płacić to pomyśl bo to jest bajecznie proste

pozdr.
Łukasz