Количество простых циклов в неориентированном графе с N вершинами

Дан неориентированный невзвешенный граф из N вершин в виде матрицы смежности adj[][] , задача состоит в том, чтобы найти количество простых циклов в нем.

Input: adj[][] = { { 0, 1, 1, 1 }, { 1, 0, 1, 0 }, { 1, 1, 0, 1 }, { 1, 0, 1, 0 } }
Output: 2
Explanation: The graph is shown below as: 

The given graph consists of two simple cycles as shown
Input: adj[][] = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 }, { 0, 1, 1, 0 } }     
Output: 1

Подход: данная проблема может быть решена с помощью динамического программирования с битовой маской, состояние динамического программирования для гамильтоновых путей определяется как dp[mask][i] как количество путей, которые покрывают маску набора узлов и заканчиваются на i и выполнять итерацию от 0 до N-1 и на каждой итерации вычислять количество циклов, содержащих текущий узел без предыдущего узла, и суммировать их. Поскольку для цикла есть два направления, разделите результат на 2 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную ans как 0 , которая хранит результирующее количество циклов.
• Инициализируйте двумерный массив dp[][] массив размерностей 2 ^N и N и инициализируйте его с 0 .
• Перебрать диапазон [0, 2 ^N – 1) , используя маску переменной, и выполнить следующие задачи:
  • Инициализируйте 2 переменные nodeSet и firstSetBit как количество установленных битов и первый установленный бит в mask .
  • Если nodeSet равен 1, установите значение dp[mask][firstSetBit] равным 1 .
  • Теперь для каждой маски, в которой установлены биты больше 1 , выполните итерацию по диапазону [firstSetBit + 1, N – 1), используя переменную j , и если побитовое И маски и 2 ^j истинно , затем инициализируйте переменную newNodeSet как mask^ 2 ^j и выполнить итерацию по диапазону [0, N) с использованием переменной k и выполнить следующие задачи:
    • Проверяем, есть ли ребро между вершинами k и j ( k не равно j) .
    • Если есть ребро, добавьте количество петель в этой маске, которая заканчивается на k и не содержит j , к состоянию для маски набора узлов следующим образом : dp[mask][j] = dp[mask][j]+ dp[маска XOR 2 ^j ][k] .
    • Если adj[j][firstSetBit] равно 1 , а nodeSet больше 2, добавьте значение dp[mask][j] к переменной ans .
• После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O((2 ^N )N ² )
Вспомогательное пространство: O(1)