Maximice el recuento de Nodes desconectados de todos los demás Nodes en un gráfico

Dados dos números enteros N y E que denotan el número de Nodes y el número de aristas de un gráfico no dirigido , la tarea es maximizar el número de Nodes que no están conectados a ningún otro Node en el gráfico, sin utilizar bucles automáticos.

Ejemplos:

Entrada: N = 5, E = 1 
Salida: 3 
Explicación: 
Dado que solo hay 1 borde en el gráfico que se puede usar para conectar dos Nodes. 
Por lo tanto, tres Nodes permanecen desconectados.

Entrada: N = 5, E = 2 
Salida: 2

Enfoque: el enfoque se basa en la idea de que para maximizar la cantidad de Nodes desconectados, los nuevos Nodes no se agregarán al gráfico hasta que cada dos Nodes distintos se conecten. A continuación se detallan los pasos para solucionar este problema:

1. Inicialice dos variables curr y rem para almacenar los Nodes conectados y los bordes que quedan sin asignar respectivamente.
2. Si rem se convierte en 0, entonces la respuesta requerida será N – curr .
3. De lo contrario, incremente el valor de curr en 1.
4. Por lo tanto, los bordes máximos necesarios en el paso actual para mantener cada dos Nodes distintos conectados son min(rem, curr) . Réstelo de rem e incremente curr .
5. Repita este proceso hasta que rem se reduzca a cero.
6. Finalmente, imprima N – curr .

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

// C++ implementation of
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function which returns
// the maximum number of
// isolated nodes
int maxDisconnected(int N, int E)
{
    // Used nodes
    int curr = 1;
 
    // Remaining edges
    int rem = E;
 
    // Count nodes used
    while (rem > 0) {
        rem = rem
              - min(
                    curr, rem);
        curr++;
    }
 
    // If given edges are non-zero
    if (curr > 1) {
        return N - curr;
    }
    else {
        return N;
    }
}
 
// Driver Code
int main()
{
    // Given N and E
    int N = 5, E = 1;
 
    // Function Call
    cout << maxDisconnected(N, E);
 
    return 0;
}

// Java implementation of
// the above approach
import java.util.*;
 
class GFG{
 
// Function which returns
// the maximum number of
// isolated nodes
static int maxDisconnected(int N, int E)
{
     
    // Used nodes
    int curr = 1;
 
    // Remaining edges
    int rem = E;
 
    // Count nodes used
    while (rem > 0)
    {
        rem = rem - Math.min(
                    curr, rem);
        curr++;
    }
 
    // If given edges are non-zero
    if (curr > 1)
    {
        return N - curr;
    }
    else
    {
        return N;
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N and E
    int N = 5, E = 1;
 
    // Function call
    System.out.print(maxDisconnected(N, E));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of
# the above approach
 
# Function which returns
# the maximum number of
# isolated nodes
def maxDisconnected(N, E):
 
    # Used nodes
    curr = 1
 
    # Remaining edges
    rem = E
 
    # Count nodes used
    while (rem > 0):
        rem = rem - min(curr, rem)
        curr += 1
 
    # If given edges are non-zero
    if (curr > 1):
        return N - curr
    else:
        return N
 
# Driver Code
if __name__ == '__main__':
 
    # Given N and E
    N = 5
    E = 1
 
    # Function call
    print(maxDisconnected(N, E))
 
# This code is contributed by mohit kumar 29

// C# implementation of
// the above approach
using System;
class GFG{
 
// Function which returns
// the maximum number of
// isolated nodes
static int maxDisconnected(int N,
                           int E)
{   
  // Used nodes
  int curr = 1;
 
  // Remaining edges
  int rem = E;
 
  // Count nodes used
  while (rem > 0)
  {
    rem = rem - Math.Min(curr, rem);
    curr++;
  }
 
  // If given edges are non-zero
  if (curr > 1)
  {
    return N - curr;
  }
  else
  {
    return N;
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given N and E
  int N = 5, E = 1;
 
  // Function call
  Console.Write(maxDisconnected(N, E));
}
}
  
// This code is contributed by 29AjayKumar

<script>
// Javascript implementation of
// the above approach
  
// Function which returns
// the maximum number of
// isolated nodes
function maxDisconnected(N,E)
{
    // Used nodes
    let curr = 1;
  
    // Remaining edges
    let rem = E;
  
    // Count nodes used
    while (rem > 0)
    {
        rem = rem - Math.min(
                    curr, rem);
        curr++;
    }
  
    // If given edges are non-zero
    if (curr > 1)
    {
        return N - curr;
    }
    else
    {
        return N;
    }
}
 
// Driver Code
 
// Given N and E
let N = 5, E = 1;
 
// Function call
document.write(maxDisconnected(N, E));
 
 
// This code is contributed by unknown2108
</script>

3

Complejidad temporal: O(E) 
Espacio auxiliar: O(1)