Número de gráficos simples con N vértices y M aristas

Dados dos enteros N y M , la tarea es contar el número de grafos simples no dirigidos que se pueden dibujar con N vértices y M aristas . Un gráfico simple es un gráfico que no contiene múltiples aristas ni bucles automáticos.

Ejemplos: 

Entrada: N = 3, M = 1 
Salida: 3 
Los 3 gráficos son {1-2, 3}, {2-3, 1}, {1-3, 2}.

Entrada: N = 5, M = 1 
Salida: 10 

Aproximación: Los N vértices están numerados del 1 al N. Como no hay bucles automáticos ni aristas múltiples, la arista debe estar presente entre dos vértices diferentes. Entonces, la cantidad de formas en que podemos elegir dos vértices diferentes es ^N C ₂ , que es igual a (N * (N – 1)) / 2 . Supóngalo P. _ 
Ahora se deben usar M aristas con estos pares de vértices, por lo que el número de formas de elegir M pares de vértices entre P pares será ^P C _M . 
Si P < M entonces la respuesta será 0ya que los bordes adicionales no se pueden dejar solos.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the value of
// Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
 
    if (k > n)
        return 0;
 
    int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n * (n - 1) *---* (n - k + 1)] / [k * (k - 1) * ... * 1]
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// Driver Code
int main()
{
    int N = 5, M = 1;
 
    int P = (N * (N - 1)) / 2;
 
    cout << binomialCoeff(P, M);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
    // Function to return the value of
    // Binomial Coefficient C(n, k)
    static int binomialCoeff(int n, int k)
    {
 
        if (k > n)
            return 0;
 
        int res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;
 
        // Calculate the value of
        // [n * (n - 1) *---* (n - k + 1)] /
        // [k * (k - 1) * ... * 1]
        for (int i = 0; i < k; ++i)
        {
            res *= (n - i);
            res /= (i + 1);
        }
        return res;
    }
 
// Driver Code
public static void main(String[] args)
{
    int N = 5, M = 1;
    int P = (N * (N - 1)) / 2;
 
    System.out.println(binomialCoeff(P, M));
}
}
 
// This code is contributed by Shivi_Aggarwal

# Python 3 implementation of the approach
 
# Function to return the value of
# Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
 
    if (k > n):
        return 0
 
    res = 1
 
    # Since C(n, k) = C(n, n-k)
    if (k > n - k):
        k = n - k
 
    # Calculate the value of
    # [n * (n - 1) *---* (n - k + 1)] /
    # [k * (k - 1) * ... * 1]
    for i in range( k):
        res *= (n - i)
        res //= (i + 1)
 
    return res
 
# Driver Code
if __name__=="__main__":
     
    N = 5
    M = 1
 
    P = (N * (N - 1)) // 2
 
    print(binomialCoeff(P, M))
 
# This code is contributed by ita_c

// C# implementation of the approach
using System;
 
class GFG
{
// Function to return the value of
// Binomial Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
 
    if (k > n)
        return 0;
 
    int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n * (n - 1) *---* (n - k + 1)] /
    // [k * (k - 1) * ... * 1]
    for (int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// Driver Code
public static void Main()
{
    int N = 5, M = 1;
 
    int P = (N * (N - 1)) / 2;
 
    Console.Write(binomialCoeff(P, M));
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP implementation of the approach
 
// Function to return the value of
// Binomial Coefficient C(n, k)
function binomialCoeff($n, $k)
{
    if ($k > $n)
        return 0;
 
    $res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if ($k > $n - $k)
        $k = $n - $k;
 
    // Calculate the value of
    // [n * (n - 1) *---* (n - k + 1)] /
    // [k * (k - 1) * ... * 1]
    for ($i = 0; $i < $k; ++$i)
    {
        $res *= ($n - $i);
        $res /= ($i + 1);
    }
 
    return $res;
}
 
// Driver Code
$N = 5;
$M = 1;
 
$P = floor(($N * ($N - 1)) / 2);
 
echo binomialCoeff($P, $M);
 
// This code is contributed by Ryuga
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return the value of
// Binomial Coefficient C(n, k)
function binomialCoeff(n, k)
{
 
    if (k > n)
        return 0;
 
    var res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n * (n - 1) *---* (n - k + 1)] / [k * (k - 1) * ... * 1]
    for (var i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// Driver Code
var N = 5, M = 1;
var P = (N * (N - 1)) / 2;
document.write( binomialCoeff(P, M));
 
</script>

10

Complejidad temporal: O(M), donde M es el número de aristas.

Complejidad espacial: O(1), ya que no se ha tomado espacio extra.