Número de ciclo hamiltoniano

Dado un gráfico completo no dirigido de N vértices donde N > 2, la tarea es encontrar el número de ciclos hamiltonianos diferentes del gráfico.
Gráfico completo : se dice que un gráfico está completo si cada uno de los vértices posibles está conectado a través de un borde.
Ciclo hamiltoniano: Es un recorrido cerrado tal que cada vértice se visita como máximo una vez excepto el vértice inicial. y no es necesario visitar todos los bordes.
Fórmula: 
 

Ejemplos: 
 

Input : N = 6
Output : Hamiltonian cycles = 60

Input : N = 4
Output : Hamiltonian cycles = 3

Explicación: 
Tomemos el ejemplo de N = 4 gráficos no dirigidos completos. Los 3 ciclos hamiltonianos diferentes se muestran a continuación:
 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program for implementation of the
// above program
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that calculates
// number of Hamiltonian cycle
int Cycles(int N)
{
 
    int fact = 1, result = 0;
 
    result = N - 1;
 
    // Calculating factorial
    int i = result;
    while (i > 0) {
        fact = fact * i;
        i--;
    }
 
    return fact / 2;
}
 
// Driver code
int main()
{
    int N = 5;
 
    int Number = Cycles(N);
 
    cout << "Hamiltonian cycles = " << Number;
    return 0;
}

// Java program for implementation
// of the above program
class GFG
{
     
// Function that calculates
// number of Hamiltonian cycle
static int Cycles(int N)
{
    int fact = 1, result = 0;
 
    result = N - 1;
 
    // Calculating factorial
    int i = result;
    while (i > 0)
    {
        fact = fact * i;
        i--;
    }
 
    return fact / 2;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 5;
 
    int Number = Cycles(N);
 
    System.out.println("Hamiltonian cycles = " +
                                        Number);
}
}
 
// This code is contributed
// by Code_Mech.

# Python3 program for implementation
# of the above program
import math as mt
 
# Function that calculates
# number of Hamiltonian cycle
def Cycles(N):
 
    fact = 1
 
    result = N - 1
 
    # Calculating factorial
    i = result
    while (i > 0):
        fact = fact * i
        i -= 1
     
    return fact // 2
 
# Driver code
N = 5
 
Number = Cycles(N)
 
print("Hamiltonian cycles = ",
                       Number)
 
# This code is contributed
# by Mohit Kumar

// C# program for implementation of
// the above program
using System;
 
class GFG
{
 
// Function that calculates
// number of Hamiltonian cycle
static int Cycles(int N)
{
    int fact = 1, result = 0;
 
    result = N - 1;
 
    // Calculating factorial
    int i = result;
    while (i > 0)
    {
        fact = fact * i;
        i--;
    }
 
    return fact / 2;
}
 
// Driver code
public static void Main()
{
    int N = 5;
 
    int Number = Cycles(N);
 
    Console.Write("Hamiltonian cycles = " +
                                   Number);
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP program for implementation
// of the above program
 
// Function that calculates
// number of Hamiltonian cycle
function Cycles($N)
{
    $fact = 1 ;
    $result = 0;
 
    $result = $N - 1;
 
    // Calculating factorial
    $i = $result;
    while ($i > 0)
    {
        $fact = $fact * $i;
        $i--;
    }
 
    return floor($fact / 2);
}
 
// Driver code
$N = 5;
 
$Number = Cycles($N);
 
echo "Hamiltonian cycles = ",
                     $Number;
 
// This code is contributed by Ryuga
?>

<script>
 
// Javascript program for implementation of the
// above program
 
// Function that calculates
// number of Hamiltonian cycle
function Cycles(N)
{
 
    var fact = 1, result = 0;
 
    result = N - 1;
 
    // Calculating factorial
    var i = result;
    while (i > 0) {
        fact = fact * i;
        i--;
    }
 
    return fact / 2;
}
 
// Driver code
var N = 5;
var Number = Cycles(N);
document.write( "Hamiltonian cycles = " + Number);
 
// This code is contributed by rutvik_56.
</script>

Hamiltonian cycles = 12

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)