fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool canConstructTree(int n, int d, int l) {
  5.     // Base cases
  6.     if (l > n) return false;  // Can't have more leaves than nodes
  7.     if (n == 2) return (d == 1 && l == 2);  // Special case for 2 nodes
  8.  
  9.     // For d = 1, only star graph is possible
  10.     if (d == 1) return (n - 1 == l);
  11.  
  12.     // For d = 2, we need a central node with leaves
  13.     if (d == 2) return (l <= n - 1 && l >= 2);
  14.  
  15.     // For d >= 3:
  16.     // Maximum possible leaves = n - (d-1) + 1
  17.     // (path of length d needs d nodes, remaining can be leaves)
  18.     int maxLeaves = n - (d - 1);
  19.  
  20.     // Minimum possible leaves = 2
  21.     // (at the ends of diameter path)
  22.     return (l >= 2 && l <= maxLeaves);
  23. }
  24.  
  25. void constructTree(int n, int d, int l) {
  26.     if (!canConstructTree(n, d, l)) {
  27.         cout << -1 << "\n";
  28.         return;
  29.     }
  30.  
  31.     if (d == 1) {
  32.         // Star graph
  33.         for (int i = 2; i <= n; i++) {
  34.             cout << "1 " << i << "\n";
  35.         }
  36.         return;
  37.     }
  38.  
  39.     if (d == 2) {
  40.         // Center node with leaves
  41.         int center = 1;
  42.         int nonLeaves = n - l;
  43.  
  44.         // Connect center to non-leaf nodes (if any besides center)
  45.         for (int i = 2; i <= nonLeaves; i++) {
  46.             cout << center << " " << i << "\n";
  47.         }
  48.  
  49.         // Connect remaining nodes as leaves
  50.         for (int i = nonLeaves + 1; i <= n; i++) {
  51.             cout << center << " " << i << "\n";
  52.         }
  53.         return;
  54.     }
  55.  
  56.     // For d >= 3:
  57.     // First create the diameter path
  58.     for (int i = 1; i < d; i++) {
  59.         cout << i << " " << i + 1 << "\n";
  60.     }
  61.  
  62.     // Remaining nodes will be attached appropriately to maintain diameter d
  63.     int nextNode = d + 1;
  64.     int midPoint = (d + 1) / 2;
  65.  
  66.     // Need to have exactly l leaves
  67.     int currentLeaves = 2;  // ends of diameter path
  68.  
  69.     // Attach remaining nodes to middle of path until we get required leaves
  70.     while (nextNode <= n) {
  71.         if (currentLeaves < l) {
  72.             // Add as leaf
  73.             cout << midPoint << " " << nextNode << "\n";
  74.             currentLeaves++;
  75.         } else {
  76.             // Add as non-leaf to maintain diameter
  77.             cout << midPoint << " " << nextNode << "\n";
  78.         }
  79.         nextNode++;
  80.     }
  81. }
  82.  
  83. int main() {
  84.     ios_base::sync_with_stdio(false);
  85.     cin.tie(nullptr);
  86.  
  87.     int t;
  88.     cin >> t;
  89.  
  90.     while (t--) {
  91.         int n, d, l;
  92.         cin >> n >> d >> l;
  93.         constructTree(n, d, l);
  94.     }
  95.  
  96.     return 0;
  97. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
2
3 2 3
4 2 3
stdout
copy 
-1
1 2
1 3
1 4
https://ideone.com/5OMmqX
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!