Chương trình C ++ để xây dựng đồ thị với các điều kiện nhất định

Giả sử chúng ta có hai số N và K. Xét có một đồ thị vô hướng với N phần tử. N đỉnh thỏa mãn các điều kiện sau -

Biểu đồ đơn giản và được kết nối
Các ngành dọc được đánh số từ 1 đến N
Gọi M là số cạnh của đồ thị. Các cạnh được đánh số từ 1 đến M. Độ dài của cạnh là 1. Và Cạnh i nối đỉnh U [i] với đỉnh V [i].
Có đúng K cặp đỉnh (i, j) trong đó i

Nếu đồ thị như vậy tồn tại, chúng ta phải xây dựng đồ thị đó. Nếu không, trả về -1.

Vì vậy, nếu đầu vào giống như N =5; K =3, thì đầu ra sẽ là

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

5, 3

Đầu ra