โปรแกรม C++ สร้างกราฟที่มีคู่โหนดระยะ 2 จำนวน K คู่

คำอธิบายปัญหา

สมมติว่าเรามีตัวเลข 2 ตัวคือ N และ K พิจารณากราฟไม่มีทิศทาง N โหนด โหนดต้องเงื่อนไข:

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

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

ตัวอย่าง: N = 5; K = 3 ผลลัพธ์เป็นกราฟตามภาพ

ขั้นตอนการแก้ปัญหา

ถ้า k > (n-1)*(n-2)/2: พิมพ์ -1
พิมพ์ ((n-1)*(n-2)/2 - k + n - 1)
สำหรับ i := 1 ถึง n-1: พิมพ์คู่ (1, i+1)
count := (n-1)*(n-2)/2 - k
สำหรับ i := 2 ถึง n:
    สำหรับ j := i+1 ถึง n:
        ถ้า count <= 0: คืน
        พิมพ์คู่ (i, j)
        ลด count ลง 1

ตัวอย่างโค้ด C++

#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

เอาต์พุต