C++ प्रोग्राम कुछ शर्तों के साथ ग्राफ बनाने के लिए

मान लीजिए कि हमारे पास दो नंबर एन और के हैं। विचार करें कि एन तत्वों के साथ एक अप्रत्यक्ष ग्राफ है। N शीर्ष निम्नलिखित शर्तों को पूरा करते हैं -

ग्राफ़ सरल और जुड़ा हुआ है
शीर्षों की संख्या 1 से N तक होती है
मान लीजिए कि ग्राफ में किनारों की संख्या M है। किनारों को 1 से M तक क्रमांकित किया गया है। किनारे की लंबाई 1 है। और किनारा i शीर्ष U[i] को शीर्ष V[i] से जोड़ता है।
शीर्षों के ठीक K जोड़े हैं (i, j) जहां i

यदि ऐसा ग्राफ मौजूद है, तो हमें वह ग्राफ बनाना होगा। अन्यथा वापसी -1.

तो, अगर इनपुट एन =5 की तरह है; K =3, तो आउटपुट होगा

कदम

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

if k > (n - 1) * (n - 2) / 2, then:
   print -1
print ((n - 1) * (n - 2) / 2 - k + n - 1)
for initialize i := 1, when i < n, update (increase i by 1), do:
   print pair (1, i + 1)
count := (n - 1) * (n - 2) / 2 - k
for initialize i := 2, when i <= n, update (increase i by 1), do:
   for initialize j := i + 1, when j <= n, update (increase j by 1), do:
      if count <= 0, then:
         return
      print pair (i, j)
      (decrease count by 1)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int k){
   if (k > (n - 1) * (n - 2) / 2){
      cout << -1 << endl;
   }
   cout << (n - 1) * (n - 2) / 2 - k + n - 1 << '\n';
   for (int i = 1; i < n; i++){
      cout << 1 << ", " << i + 1 << '\n';
   }
   int count = (n - 1) * (n - 2) / 2 - k;
   for (int i = 2; i <= n; i++){
      for (int j = i + 1; j <= n; j++){
         if (count <= 0){
            return;
         }
         cout << i << ", " << j << '\n';
         count--;
      }
   }
}
int main(){
   int N = 5;
   int K = 3;
   solve(N, K);
}

इनपुट

5, 3

आउटपुट