โปรแกรม C++ สร้างกราฟแบบมีเงื่อนไข

สมมติว่าเรามีตัวเลขสองจำนวน N และ K พิจารณาว่ามีกราฟแบบไม่มีทิศทางที่มีองค์ประกอบ N จุดยอด N เป็นไปตามเงื่อนไขต่อไปนี้ -

กราฟเป็นแบบเรียบง่ายและเชื่อมโยง
จุดยอดมีตัวเลขตั้งแต่ 1 ถึง N
ให้ M เป็นจำนวนขอบในกราฟ ขอบมีหมายเลขตั้งแต่ 1 ถึง M ความยาวของขอบคือ 1 และขอบ i เชื่อมจุดยอด U[i] กับจุดยอด V[i]
มีจุดยอดคู่ K (i, j) โดยที่ i

หากมีกราฟดังกล่าว เราต้องสร้างกราฟนั้น มิฉะนั้น ให้ส่งคืน -1

ดังนั้นหากอินพุตเป็นเช่น N =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

ผลลัพธ์