给定直径、高度和顶点的树的可能边-yiteyi-C++库

找到具有给定值的树并打印树的边。如果无法打印树，请打印“-1”。

null

给定三个整数n，d和h。

n -> Number of vertices. [1, n]d -> Diameter of the tree (largest    distance between two vertices).h -> Height of the tree (longest distance   between vertex 1 and another vertex)

例如：

Input : n = 5, d = 3, h = 2 Output : 1 2         2 3         1 4         1 5Explanation :

图片[1]-给定直径、高度和顶点的树的可能边-yiteyi-C++库

We can see that the height of the tree is 2 (1 -> 2 --> 5) and diameter is 3 ( 3 -> 2 -> 1 -> 5).So our conditions are satisfied.Input :  n = 8, d = 4, h = 2Output : 1 2         2 3         1 4         4 5         1 6         1 7         1 8Explanation :

图片[2]-给定直径、高度和顶点的树的可能边-yiteyi-C++库

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

注意，当 d=1， 我们不能构造一棵树（如果树有两个以上的顶点）。什么时候 d>2*h ，我们不能建造一棵树。
正如我们所知，高度是从顶点1到另一个顶点的最长路径。所以，从顶点1开始，通过将边添加到h来构建路径 d>h ，我们应该添加另一条路径，以满足顶点1的直径，长度为 d–h .
我们的高度和直径条件都满足。但仍有一些顶点可能会留下。在端点以外的任何顶点添加其余顶点。这一步不会改变我们的直径和高度。选择“顶点1”以添加其余顶点（可以选择任何顶点）。
但是什么时候 d==h ，选择顶点2以添加其余顶点。

C++

                         // C++ program to construct tree for given count                       
                         // width and height.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to construct the tree                       
                         void                                     constructTree(                                     int                                     n,                                     int                                     d,                                     int                                     h)                       
                         {                       
                                                 if                                     (d == 1) {                       
           
                                                 // Special case when d == 2, only one edge                       
                                                 if                                     (n == 2 && h == 1) {                       
                                                 cout <<                                     "1 2"                                     << endl;                       
                                                 return                                     ;                       
                                                 }                       
                                                 cout <<                                     "-1"                                     << endl;                                     // Tree is not possible                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 if                                     (d > 2 * h) {                       
                                                 cout <<                                     "-1"                                     << endl;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Satisfy the height condition by add                       
                                                 // edges up to h                       
                                                 for                                     (                                     int                                     i = 1; i <= h; i++)                       
                                                 cout << i <<                                     " "                                     << i + 1 << endl;                       
                                   
                                                 if                                     (d > h) {                       
           
                                                 // Add d - h edges from 1 to                       
                                                 // satisfy diameter condition                       
                                                 cout <<                                     "1"                       
                                                 <<                                     " "                                     << h + 2 << endl;                       
                                                 for                                     (                                     int                                     i = h + 2; i <= d; i++) {                       
                                                 cout << i <<                                     " "                                     << i + 1 << endl;                       
                                                 }                       
                                                 }                       
           
                                                 // Remaining edges at vertex 1 or 2(d == h)                       
                                                 for                                     (                                     int                                     i = d + 1; i < n; i++)                       
                                                 {                       
                                                 int                                     k = 1;                       
                                                 if                                     (d == h)                       
                                                 k = 2;                       
                                                 cout << k <<                                     " "                                     << i + 1 << endl;                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 5, d = 3, h = 2;                       
                                                 constructTree(n, d, h);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to construct tree for given count                       
                         // width and height.                       
                         class                                     GfG {                       
           
                         // Function to construct the tree                       
                         static                                     void                                     constructTree(                                     int                                     n,                                     int                                     d,                                     int                                     h)                       
                         {                       
                                                 if                                     (d ==                                     1                                     ) {                       
           
                                                 // Special case when d == 2, only one edge                       
                                                 if                                     (n ==                                     2                                     && h ==                                     1                                     ) {                       
                                                 System.out.println(                                     "1 2"                                     );                       
                                                 return                                     ;                       
                                                 }                       
                                                 System.out.println(                                     "-1"                                     );                                     // Tree is not possible                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 if                                     (d >                                     2                                     * h) {                       
                                                 System.out.println(                                     "-1"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Satisfy the height condition by add                       
                                                 // edges up to h                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= h; i++)                       
                                                 System.out.println(i +                                     " "                                     + (i +                                     1                                     ));                       
                                   
                                                 if                                     (d > h) {                       
           
                                                 // Add d - h edges from 1 to                       
                                                 // satisfy diameter condition                       
                                                 System.out.println(                                     "1"                                     +                                     " "                                     + (h +                                     2                                     ));                       
                                                 for                                     (                                     int                                     i = h +                                     2                                     ; i <= d; i++) {                       
                                                 System.out.println(i +                                     " "                                     + (i +                                     1                                     ));                       
                                                 }                       
                                                 }                       
           
                                                 // Remaining edges at vertex 1 or 2(d == h)                       
                                                 for                                     (                                     int                                     i = d +                                     1                                     ; i < n; i++)                       
                                                 {                       
                                                 int                                     k =                                     1                                     ;                       
                                                 if                                     (d == h)                       
                                                 k =                                     2                                     ;                       
                                                 System.out.println(k +                                     " "                                     + (i +                                     1                                     ));                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     5                                     , d =                                     3                                     , h =                                     2                                     ;                       
                                                 constructTree(n, d, h);                       
                         }                       
                         }                       

Python3

                         # Python3 code to construct tree for given count                       
                         # width and height.                       
           
                         # Function to construct the tree                       
                         def                                     constructTree(n, d, h):                       
                                                 if                                     d                                     =                                     =                                     1                                     :                       
           
                                                 # Special case when d == 2, only one edge                       
                                                 if                                     n                                     =                                     =                                     2                                     and                                     h                                     =                                     =                                     1                                     :                       
                                                 print                                     (                                     "1 2"                                     )                       
                                                 return                                     0                       
                                   
                                                 print                                     (                                     "-1"                                     )                                     # Tree is not possible                       
                                                 return                                     0                       
                                   
                                                 if                                     d >                                     2                                     *                                     h:                       
                                                 print                                     (                                     "-1"                                     )                       
                                                 return                                     0                       
                                   
                                                 # Satisfy the height condition by add                       
                                                 # edges up to h                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , h                                     +                                     1                                     ):                       
                                                 print                                     (i,                                     " "                                     , i                                     +                                     1                                     )                       
                                   
                                                 if                                     d > h:                       
           
                                                 # Add d - h edges from 1 to                       
                                                 # satisfy diameter condition                       
                                                 print                                     (                                     1                                     ,                                     "  "                                     , h                                     +                                     2                                     )                       
                                                 for                                     i                                     in                                     range                                     (h                                     +                                     2                                     , d                                     +                                     1                                     ):                       
                                                 print                                     (i,                                     " "                                     , i                                     +                                     1                                     )                       
                                   
                                                 # Remaining edges at vertex 1 or 2(d == h)                       
                                                 for                                     i                                     in                                     range                                     (d                                     +                                     1                                     , n):                       
                                                 k                                     =                                     1                       
                                                 if                                     d                                     =                                     =                                     h:                       
                                                 k                                     =                                     2                       
                                                 print                                     (k ,                                     " "                                     , i                                     +                                     1                                     )                       
           
                         # Driver Code                       
                         n                                     =                                     5                       
                         d                                     =                                     3                       
                         h                                     =                                     2                       
                         constructTree(n, d, h)                       
           
                         # This code is contributed by "Sharad_Bhardwaj".                       

C#

                         // C# program to construct tree for                       
                         // given count width and height.                       
                         using                                     System;                       
           
                         class                                     GfG                       
                         {                       
           
                                                 // Function to construct the tree                       
                                                 static                                     void                                     constructTree(                                     int                                     n,                                     int                                     d,                                     int                                     h)                       
                                                 {                       
                                                 if                                     (d == 1)                       
                                                 {                       
           
                                                 // Special case when d == 2,                       
                                                 // only one edge                       
                                                 if                                     (n == 2 && h == 1)                       
                                                 {                       
                                                 Console.WriteLine(                                     "1 2"                                     );                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // Tree is not possible                       
                                                 Console.WriteLine(                                     "-1"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 if                                     (d > 2 * h)                       
                                                 {                       
                                                 Console.WriteLine(                                     "-1"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Satisfy the height condition                       
                                                 // by add edges up to h                       
                                                 for                                     (                                     int                                     i = 1; i <= h; i++)                       
                                                 Console.WriteLine(i +                                     " "                                     + (i + 1));                       
           
                                                 if                                     (d > h)                       
                                                 {                       
           
                                                 // Add d - h edges from 1 to                       
                                                 // satisfy diameter condition                       
                                                 Console.WriteLine(                                     "1"                                     +                                     " "                                     + (h + 2));                       
                                                 for                                     (                                     int                                     i = h + 2; i <= d; i++)                       
                                                 {                       
                                                 Console.WriteLine(i +                                     " "                                     + (i + 1));                       
                                                 }                       
                                                 }                       
           
                                                 // Remaining edges at vertex 1 or 2(d == h)                       
                                                 for                                     (                                     int                                     i = d + 1; i < n; i++)                       
                                                 {                       
                                                 int                                     k = 1;                       
                                                 if                                     (d == h)                       
                                                 k = 2;                       
                                                 Console.WriteLine(k +                                     " "                                     + (i + 1));                       
                                                 }                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     n = 5, d = 3, h = 2;                       
                                                 constructTree(n, d, h);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Javascript

                         <script>                       
           
                         // Javascript program to construct tree for                       
                         // given count width and height.                       
           
                         // Function to construct the tree                       
                         function                                     constructTree(n, d, h)                       
                         {                       
                                                 if                                     (d == 1)                       
                                                 {                       
                                   
                                                 // Special case when d == 2,                       
                                                 // only one edge                       
                                                 if                                     (n == 2 && h == 1)                       
                                                 {                       
                                                 document.write(                                     "1 2"                                     ,                                     "<br>"                                     );                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // Tree is not possible                       
                                                 document.write(                                     "-1"                                     ,                                     "<br>"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 if                                     (d > 2 * h)                       
                                                 {                       
                                                 document.write(                                     "-1"                                     ,                                     "<br>"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Satisfy the height condition                       
                                                 // by add edges up to h                       
                                                 for                                     (                                     var                                     i = 1; i <= h; i++)                       
                                                 document.write(i +                                     " "                                     + (i + 1),                                     "<br>"                                     );                       
           
                                                 if                                     (d > h)                       
                                                 {                       
                                   
                                                 // Add d - h edges from 1 to                       
                                                 // satisfy diameter condition                       
                                                 document.write(                                     "1"                                     +                                     " "                                     + (h + 2),                                     "<br>"                                     );                       
                                                 for                                     (                                     var                                     i = h + 2; i <= d; i++)                       
                                                 {                       
                                                 document.write(i +                                     " "                                     + (i + 1),                                     "<br>"                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // Remaining edges at vertex 1 or 2(d == h)                       
                                                 for                                     (                                     var                                     i = d + 1; i < n; i++)                       
                                                 {                       
                                                 var                                     k = 1;                       
                                                 if                                     (d == h)                       
                                                 k = 2;                       
                                   
                                                 document.write(k +                                     " "                                     + (i + 1),                                     "<br>"                                     );                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         var                                     n = 5, d = 3, h = 2;                       
           
                         constructTree(n, d, h);                       
           
                         // This code is contributed by bunnyram19                       
           
                         </script>                       

输出：

1 22 31 41 5

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章