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.

Przypadki testowe

Przypadki testowe jako macierze adiakencji

code-golf decision-problem graph-theory Kreator pszenicy
źródło

Czy możesz spojrzeć na moje rozwiązanie, daj mi znać, czy jest prawidłowe? Upadłem, jakby oczywisty wzorzec był zbyt oczywisty i że coś mi umknęło.

Kudłaty

@Shaggy Nie umiem czytać JavaScript, jeśli to wyjaśnisz, być może będę w stanie.

Kreator pszenicy

Mogę spróbować. Sprawdzam 2 rzeczy: 1) Czy 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].

Kudłaty

@Shaggy To nie działa, na przykład pierwszy podany schemat nie działa.

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]]))

Kreator pszenicy

Gdyby że zwrot truelub false?

Kudłaty

Czy to kaktus?

Definicje

Zadanie

Odpowiedzi:

Mathematica, 62 bajty