В теории графов Кактус - это связный граф, в котором любые два простых цикла в графе имеют не более одной вершины.

Вот Кактус с 3 простыми циклами, обведенными пунктирными линиями.

Следующий график похож на изображенный выше, но не является Кактусом, потому что две вершины, помеченные красным, разделены двумя простыми циклами.

Все может стать немного сложнее, например, следующий график:

Может выглядеть как Кактус, но это не так. Это можно показать, выделив следующий цикл:

Этот цикл имеет более чем одну точку со многими более очевидными циклами на графике.

Определения

Связный граф - это такой граф, что между любыми двумя вершинами существует хотя бы один путь.
Простой цикл - это путь на графе, который начинается и заканчивается в одной и той же вершине и не посещает ни одну вершину более одного раза.
Простой граф - это неориентированный, невзвешенный граф, такой, что никакие вершины не связаны друг с другом более чем одним ребром, и никакая вершина не связана с самим собой. Простой график - это самый основной тип графика, и это то, что большинство людей имеет в виду, когда говорят «график».

задача

Возьмите простой граф в качестве входных данных и решите, является ли он графом Кактуса. Вы должны вывести два различных значения, одно для Истины и одно для Ложных. Вы можете принять участие в любом формате, который вы считаете нужным.

Это код-гольф, поэтому вы должны стремиться минимизировать количество байтов ваших ответов.

Тестовые случаи

Тестовые случаи как матрицы смежности

code-golf decision-problem graph-theory Мастер пшеницы
источник

Можете ли вы взглянуть на мое решение, дайте мне знать, если оно действительно? Я упал, как будто очевидная модель была слишком очевидна, и что я что-то упустил.

Лохматый

@ Shaggy Я не могу читать JavaScript, если вы объясните это, я смогу.

Пшеничный волшебник

Я могу попробовать. Я проверяю 2 вещи: 1) Содержит ли eровно один элемент И vсодержит ли ровно 2 И vравен первому элементу e? 2) ИЛИ vравен множеству объединения первых элементов каждого элемента в e? Второй тест проходит первый чек ( v=[1,2]=e[0]=[1,2]) и другие тесты , которые должны быть истинный матчем вторыми, например , случай # 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].

Лохматый

@ Shaggy Это не работает, например, первая приведенная схема не работает.

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

Пшеничный волшебник

Это должно вернуться trueили false?

Лохматый

Это Кактус?

Определения

задача

Ответы:

Mathematica, 62 байта