Maximice la cantidad de Nodes que no forman parte de ningún borde en un gráfico

Dado un grafo con n Nodes y m aristas. Encuentre el máximo número posible de Nodes que no forman parte de ningún borde (m siempre será menor o igual que un número de bordes en el gráfico completo).
Ejemplos: 
 

Input: n = 3, m = 3
Output: Maximum Nodes Left Out: 0
Since it is a complete graph.

Input: n = 7, m = 6 
Output: Maximum Nodes Left Out: 3
We can construct a complete graph on 4 vertices using 6 edges.

Enfoque: iterar sobre todos los n y ver en qué número de Nodes si hacemos un gráfico completo obtenemos un número de aristas más que m dicen que es K. La respuesta es nk . 
 

• El número máximo de aristas que se pueden usar para formar un gráfico en n Nodes es n * (n – 1) / 2 (un gráfico completo).
• Luego encuentre el número de n máximo, que usará m o menos de m aristas para formar un gráfico completo.
• Si todavía quedan aristas, entonces cubrirá solo un Node más, como si hubiera cubierto más de un Node que, este no es el valor máximo de n.

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

// C++ program to illustrate above approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to return number of nodes left out
int answer(int n, int m)
{
    int i;
    for (i = 0; i <= n; i++) {
 
        // Condition to terminate, when
        // m edges are covered
        if ((i * (i - 1)) >= 2 * m)
            break;
    }
 
    return n - i;
}
 
// Driver Code
int main()
{
    int n = 7;
    int m = 6;
    cout << answer(n, m) << endl;
}

// Java program to illustrate above approach
 
import java.io.*;
 
class GFG {
 
// Function to return number of nodes left out
static int answer(int n, int m)
{
    int i;
    for (i = 0; i <= n; i++) {
 
        // Condition to terminate, when
        // m edges are covered
        if ((i * (i - 1)) >= 2 * m)
            break;
    }
 
    return n - i;
}
 
        // Driver Code
    public static void main (String[] args) {
        int n = 7;
    int m = 6;
    System.out.print( answer(n, m));
    }
}
// This code is contributed by anuj_67..

# Python 3 program to illustrate
# above approach
 
# Function to return number of
# nodes left out
def answer(n, m):
    for i in range(0, n + 1, 1):
         
        # Condition to terminate, when
        # m edges are covered
        if ((i * (i - 1)) >= 2 * m):
            break
     
    return n - i
 
# Driver Code
if __name__ == '__main__':
    n = 7
    m = 6
    print(answer(n, m))
 
# This code is contributed
# by Surendra_Gangwar

// C# program to illustrate
// above approach
using System;
 
class GFG
{
     
// Function to return number
// of nodes left out
static int answer(int n, int m)
{
    int i;
    for (i = 0; i <= n; i++)
    {
 
        // Condition to terminate, when
        // m edges are covered
        if ((i * (i - 1)) >= 2 * m)
            break;
    }
 
    return n - i;
}
 
// Driver Code
static public void Main ()
{
    int n = 7;
    int m = 6;
    Console.WriteLine(answer(n, m));
}
}
 
// This code is contributed
// by anuj_67

<?php
// PHP program to illustrate
// above approach
 
// Function to return number
// of nodes left out
function answer($n, $m)
{
    for ($i = 0; $i <= $n; $i++)
    {
 
        // Condition to terminate, when
        // m edges are covered
        if (($i * ($i - 1)) >= 2 * $m)
            break;
    }
 
    return $n - $i;
}
 
// Driver Code
$n = 7;
$m = 6;
echo answer($n, $m) + "\n";
 
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

<script>
 
// Javascript implementation of the above approach
 
// Function to return number of nodes left out
function answer(n, m)
{
    let i;
    for (i = 0; i <= n; i++) {
 
        // Condition to terminate, when
        // m edges are covered
        if ((i * (i - 1)) >= 2 * m)
            break;
    }
 
    return n - i;
}
 
// driver program
     
    let n = 7;
    let m = 6;
    document.write( answer(n, m));
   
</script>

3

Complejidad temporal: O(n) donde n es el número de Nodes.
Espacio Auxiliar: O(1)