I have searched for a while and found multiple algorithms to

CodePudding user response：

Start with an adjacency matrix M such that there is a 1 at row j, column i if there is an arc from vertex i to vertex j, and 0 otherwise. Note the ordering -- each vertex's arcs are represented by a column in this matrix, so it's the transpose of the more common row-major order for adjacency matrices.

Now, If we define a vertex vector V_i to be a column vector that has a 1 in row i and 0 everywhere else, then the product MV_i gives the number of ways that you can get from vertex i to every other vertex in one step. The sum of the diagonal elements is the number of length-1 cycles.

Using matrix exponentiation-by-squaring, you can calculate Mⁿ in O(|V|³ log n) time†. For every vertex vector, then MⁿV_i gives the number of ways you can get from vertex i to every other vertex in n steps, and the sum of the diagonal elements of Mⁿ is the total number of length-n cycles.

† - caveat: the O(|V|³ log n) time assumes constant times for mathematical operations, which is not necessarily true, since the numbers involved can get very large.

CodePudding user response：

Performance note. Set n to be the size of the graph, and you have the Hamiltonian Cycle problem. This is well-known to be NP-complete. Conversely this means that, even if you were told the n points that contain the cycle, verifying that there is a cycle of length n in those points is still hard.

Therefore while producing a correct algorithm isn't that hard, producing an efficient one is a different story.