Haz un árbol con n vértices, d diámetro y como máximo grado de vértice k

Dados tres números enteros N , D y K . La tarea es verificar si es posible hacer un árbol con exactamente N vértices, D diámetro (el número de aristas en el camino más largo entre dos vértices) y el grado de cada vértice debe ser como máximo K . Si es posible, imprima todos los bordes posibles; de lo contrario, imprima No.

Ejemplos: 

Entrada: N = 6, D = 3, K = 4 
Salida: 
1 2 
2 3 
3 4 
5 2 
6 2 
 

Entrada: N = 6, D = 2, K = 4 
Salida: N0 
 

Enfoque: Construyamos el árbol con el siguiente algoritmo: Si (d > n – 1), imprima “No” y finalice el programa. De lo contrario, mantengamos el arreglo grados de la longitud n que representará los grados de los vértices.
El primer paso es construir el diámetro del árbol. Dejemos que los primeros (d + 1) vértices lo formen. 

Agreguemos d aristas a la respuesta y aumentemos los grados de los vértices correspondientes a estas aristas, y si algún vértice tiene un grado mayor que k, imprima «No» y finalice el programa.

El segundo (y último) paso es adjuntar los vértices restantes (n – d – 1) al árbol. Llamemos libre al vértice si su grado es menor que k. Además, mantengamos todos los vértices libres que forman el diámetro en alguna estructura de datos que nos permita tomar el vértice con la distancia máxima mínima a cualquier otro vértice y eliminar dichos vértices. Se puede hacer, por ejemplo, mediante un conjunto de pares (dist _v , v), donde dist _ves la distancia máxima del vértice v a cualquier otro vértice. Ahora agreguemos todos los vértices comenzando desde el vértice (d + 1) (0-indexado) al vértice n?1, sea u el vértice actual. Uno puede obtener el vértice con la mínima distancia máxima a cualquier otro vértice, sea v. Ahora aumente el grado de los vértices u y v, agregue el borde entre ellos, y si v todavía está libre, devuélvalo a la estructura de datos, de lo contrario, quítelo. Lo mismo con el vértice u (es obvio que su distancia máxima a cualquier otro vértice será igual a (dist _v + 1).

Si en algún paso nuestra estructura de datos estará vacía o la distancia máxima mínima será igual a d, la respuesta es “No”. De lo contrario, podemos imprimir la respuesta.

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 Make a tree with n vertices, d as it's
// diameter and degree of each vertex is at most k
void Make_tree(int n, int d, int k)
{
    // If diameter > n - 1
    // impossible to build tree
    if (d > n - 1) {
        cout << "No";
        return;
    }
 
    // To store the degree of each vertex
    vector<int> deg(n);
 
    // To store the edge between vertices
    vector<pair<int, int> > ans;
 
    // To store maximum distance among
    // all the paths from a vertex
    set<pair<int, int> > q;
 
    // Make diameter of tree equals to d
    for (int i = 0; i < d; ++i) {
        ++deg[i];
        ++deg[i + 1];
        if (deg[i] > k || deg[i + 1] > k) {
            cout << "NO" << endl;
            return;
        }
 
        // Add an edge between them
        ans.push_back(make_pair(i, i + 1));
    }
 
    // Store maximum distance of each vertex
    // from other vertices
    for (int i = 1; i < d; ++i)
        q.insert(make_pair(max(i, d - i), i));
 
    // For next (n - d - 1) edges
    for (int i = d + 1; i < n; ++i) {
 
        // If the vertex already has the degree k
        while (!q.empty() && deg[q.begin()->second] == k)
            q.erase(q.begin());
 
        // If not possible
        if (q.empty() || q.begin()->first == d) {
            cout << "No";
            return;
        }
 
        // Increase the degree of vertices
        ++deg[i];
        ++deg[q.begin()->second];
 
        // Add an edge between them
        ans.push_back(make_pair(i, q.begin()->second));
 
        // Store the maximum distance of this vertex
        // from other vertices
        q.insert(make_pair(q.begin()->first + 1, i));
    }
 
    // Print all the edges of the built tree
    for (int i = 0; i < n - 1; ++i)
        cout << ans[i].first + 1 << " "
             << ans[i].second + 1 << endl;
}
 
// Driver code
int main()
{
    int n = 6, d = 3, k = 4;
    Make_tree(n, d, k);
 
    return 0;
}

# Python3 implementation of the approach
 
# Function to Make a tree with n vertices, d as it's
# diameter and degree of each vertex is at most k
def Make_tree(n, d, k):
     
    # If diameter > n - 1
    # impossible to build tree
    if (d > n - 1):
        print("No")
        return
 
    # To store the degree of each vertex
    deg = [0]*(n)
 
    # To store the edge between vertices
    ans = []
 
    # To store maximum distance among
    #all the paths from a vertex
    q = {}
 
    # Make diameter of tree equals to d
    for i in range(d):
        deg[i] += 1
        deg[i + 1] += 1
        if (deg[i] > k or deg[i + 1] > k):
            print("NO")
            return
 
        # Add an edge between them
        ans.append((i, i + 1))
 
    # Store maximum distance of each vertex
    # from other vertices
    for i in range(1, d):
        q[(max(i, d - i), i)] = 1
 
    # For next (n - d - 1) edges
    for i in range(d + 1, n):
        arr = list(q.keys())
 
        # If the vertex already has the degree k
        while (len(q) > 0 and deg[arr[0][1]] == k):
            del q[arr[0]]
 
        # If not possible
        if (len(q) == 0 or arr[0][0] == d):
            print ("No")
            return
 
        # Increase the degree of vertices
        deg[i] += 1
        deg[arr[0][1]] += 1
 
        # Add an edge between them
        ans.append((i, arr[0][1]))
 
        # Store the maximum distance of this vertex
        # from other vertices
        q[(arr[0][0] + 1, i)] = 1
 
    # Print all the edges of the built tree
    for i in range(n - 1):
        print(ans[i][0] + 1, ans[i][1]+ 1)
 
# Driver code
if __name__ == '__main__':
    n, d, k = 6, 3, 4
    Make_tree(n, d, k)
 
    # This code is contributed by mohit kumar 29.

<script>
 
// Javascript implementation of the approach
 
// Function to Make a tree with n vertices,
// d as it's diameter and degree of each
// vertex is at most k
function Make_tree(n, d, k)
{
     
    // If diameter > n - 1
    // impossible to build tree
    if (d > n - 1)
    {
        document.write("No");
        return;
    }
  
    // To store the degree of each vertex
    let deg = new Array(n);
    for(let i = 0; i < n; i++)
    {
        deg[i] = 0;
    }
  
    // To store the edge between vertices
    let ans = [];
  
    // To store maximum distance among
    // all the paths from a vertex
    let q = new Set();
  
    // Make diameter of tree equals to d
    for(let i = 0; i < d; ++i)
    {
        ++deg[i];
        ++deg[i + 1];
         
        if (deg[i] > k || deg[i + 1] > k)
        {
            document.write("NO<br>");
            return;
        }
  
        // Add an edge between them
        ans.push([i, i + 1]);
    }
  
    // Store maximum distance of each vertex
    // from other vertices
    for(let i = 1; i < d; ++i)
        q.add([Math.max(i, d - i), i]);
  
    // For next (n - d - 1) edges
    for(let i = d + 1; i < n; ++i)
    {
         let arr = Array.from(q);
          
        // If the vertex already has the degree k
        while (q.size != 0 && deg[arr[0][1]] == k)
            q.delete(arr[0]);
  
        // If not possible
        if (q.size == 0 || arr[0][0] == d)
        {
            document.write("No<br>")
            return;
        }
  
        // Increase the degree of vertices
        ++deg[i];
        ++deg[arr[0][1]];
  
        // Add an edge between them
        ans.push([i, arr[0][1]]);
  
        // Store the maximum distance of this
        // vertex from other vertices
        q.add([arr[0][0] + 1, i]);
    }
     
    // Print all the edges of the built tree
    for(let i = 0; i < n - 1; ++i)
        document.write((ans[i][0] + 1) + " " +
                       (ans[i][1] + 1) + "<br>");
}
 
// Driver code
let n = 6, d = 3, k = 4;
Make_tree(n, d, k);
 
// This code is contributed by unknown2108
 
</script>

1 2
2 3
3 4
5 2
6 2