Chương trình C++ xây dựng đồ thị thỏa mãn điều kiện khoảng cách ngắn nhất

Cho N, K. Xây dựng đồ thị vô hướng đơn, liên thông, N đỉnh (1..N), cạnh độ dài 1. Yêu cầu: có đúng K cặp đỉnh (i,j) (i<j) có khoảng cách ngắn nhất bằng 2. Nếu không tồn tại, trả về -1.

Ví dụ

Với N=5, K=3, đầu ra là đồ thị sao (star) tâm 1 nối 2,3,4,5 và thêm các cạnh (2,3), (2,4), (2,5). Tổng 7 cạnh.

Giải thuật

Số cặp khoảng cách 2 tối đa trong đồ thị sao là (N-1)*(N-2)/2. Nếu K lớn hơn giá trị này, impossible. Ngược lại, xây đồ thị sao (đỉnh 1 nối tất cả), sau đó thêm (N-1)*(N-2)/2 - K cạnh giữa các đỉnh lá để giảm số cặp khoảng cách 2.

Mã C++

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

void solve(int n, int k) {
    if (k > (n - 1) * (n - 2) / 2) {
        cout << -1 << endl;
        return;
    }
    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, K = 3;
    solve(N, K);
}

Đầu vào / Đầu ra

Input: 5, 3
Output: 7 1, 2 1, 3 1, 4 1, 5 2, 3 2, 4 2, 5