C++ প্রোগ্রাম: নির্দিষ্ট শর্তে গ্রাফ নির্মাণ করা

মান লিখুন: আমাদের কাছে দুটি সংখ্যা N এবং K রয়েছে। N ভের্টেক্স বিশিষ্ট একটি অনির্দেশিত গ্রাফ বিবেচনা করুন যেটি নিচের শর্তগুলো পূরণ করে:

গ্রাফটি সিম্পল এবং কানেক্টেড
ভার্টেক্সগুলো 1 থেকে N পর্যন্ত নম্বর দেওয়া
M সংখ্যক এজ আছে, এজগুলো 1 থেকে M পর্যন্ত নম্বর দেওয়া। প্রতিটি এজের দৈর্ঘ্য ১। এজ i ভের্টেক্স U[i] এবং V[i]-কে সংযুক্ত করে
ঠিক K জোড়া ভের্টেক্স (i, j) আছে যেখানে i < j, যাদের মধ্যে শর্টেস্ট ডিস্ট্যান্স ২

যদি এমন গ্রাফ সম্ভব হয়, তবে সেটি নির্মাণ করুন। অন্যথায় -1 রিটার্ন করুন।

উদাহরণ

যদি ইনপুট হয় N = 5; K = 3, তবে আউটপুট হবে (চিত্রে দেখানো হয়েছে)।

সমাধানের ধাপসমূহ

যদি k > (n-1)*(n-2)/2:
    -1 প্রিন্ট করুন
((n-1)*(n-2)/2 - k + n - 1) প্রিন্ট করুন
for i := 1 থেকে n-1:
    জোড়া (1, i+1) প্রিন্ট করুন
count := (n-1)*(n-2)/2 - k
for i := 2 থেকে n:
    for j := i+1 থেকে n:
        যদি count <= 0: রিটার্ন
        জোড়া (i, j) প্রিন্ট করুন
        count কমান

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, K = 3;
    solve(N, K);
}

ইনপুট

5, 3

আউটপুট