W teorii grafów kaktus jest połączonym wykresem, tak że dowolne dwa wyraźne cykle na wykresie dzielą co najwyżej jeden wierzchołek.
Oto Kaktus z 3 prostymi cyklami obrysowanymi liniami przerywanymi.
Poniższy wykres jest podobny do pokazanego powyżej, ale nie jest kaktusem, ponieważ dwa wierzchołki oznaczone kolorem czerwonym są wspólne dla dwóch prostych cykli.
Sprawy mogą być nieco trudniejsze, na przykład następujący wykres:
Może wyglądać jak kaktus, ale tak nie jest. Można to pokazać, podświetlając następujący cykl:
Cykl ten dzieli więcej niż jeden punkt z wieloma bardziej oczywistymi cyklami na wykresie.
Definicje
Połączony wykres to taki, że istnieje co najmniej jedna ścieżka między dowolnymi dwoma wierzchołkami.
Prosty cykl to ścieżka na wykresie, która zaczyna się i kończy na tym samym wierzchołku i nie odwiedza żadnego wierzchołka więcej niż jeden raz.
Prosty wykres jest niekierowanym, nieważonym wykresem, tak że żaden wierzchołek nie jest połączony ze sobą więcej niż jedną krawędzią i żaden wierzchołek nie jest połączony z samym sobą. Prosty wykres jest najbardziej podstawowym rodzajem wykresu i jest tym, co większość ludzi ma na myśli, gdy mówi wykres.
Zadanie
Weź prosty wykres jako dane wejściowe i zdecyduj, czy jest to wykres Cactus. Powinieneś wypisać dwie różne wartości: jedną dla wartości True i jedną dla wartości False. Możesz przyjmować dane wejściowe w dowolnym formacie, który Ci odpowiada.
To jest golf golfowy, więc powinieneś dążyć do zminimalizowania liczby bajtów twoich odpowiedzi.
ezawiera dokładnie jeden element AND vzawiera dokładnie 2 AND jest vrówny pierwszemu elementowi e? 2) LUB Czy jest vrówny zestawowi łączącemu pierwszych elementów każdego elementu e? Drugi sprawdzian przechodzi pierwszego wyboru ( v=[1,2]=e[0]=[1,2]) i innych przypadków testowych, które powinny być prawdziwe mecz drugi, na przykład sprawa nr 4: v=[1,2,3,4,5,6]=[e[0][0],e[1][0],e[2][0],e[4][0]]=[1,2,3,4,5,6].
console.log(f([1,2,3,4,5,6,7,8,9,10,11,12,13])([[1,2],[1,3],[3,4],[2,4],[3,5],[5,6],[6,7],[7,8],[8,5],[7,9],[9,10],[10,11],[11,7],[8,12],[8,13]]))
truelub false?