সি++-এ গ্রাফে কোনো এজের অংশ নয় এমন নোডের সর্বোচ্চ সংখ্যা নির্ণয়

একটি গ্রাফ দেওয়া আছে যাতে নোড এবং এজ আছে। লক্ষ্য হল গ্রাফে যেসব নোড কোনো এজের সাথে সংযুক্ত নয়, তাদের সর্বোচ্চ সম্ভাব্য সংখ্যা নির্ণয় করা। আমরা জানি কমপ্লিট গ্রাফে নোডের সংখ্যা সবসময় এজের সংখ্যা থেকে কম বা সমান হয়।

কমপ্লিট গ্রাফ তৈরির চেষ্টা করা হয়: যদি নোড সংখ্যা n হয়, তবে এজ সংখ্যা n(n-1)/2 হবে।

edge = n(n-1)/2 → 2*edge = n(n-1)। যখন n(n-1) > এজ সংখ্যা, তখন অতিরিক্ত নোড পাওয়া যায়। i=1 থেকে n পর্যন্ত ইটারেট করা হয়। যতক্ষণ i(i-1) > 2*edge, ততক্ষণ লুপ চলে। ফলাফল n-i।

উদাহরণ

ইনপুট: nodes=5, edges=2

আউটপুট: গ্রাফে কোনো এজের অংশ নয় এমন নোডের সর্বোচ্চ সংখ্যা: ২

ব্যাখ্যা: ২টি এজে কমপক্ষে ৩টি নোড এবং সর্বোচ্চ ৪টি নোড থাকতে পারে। ৩টি নোডের জন্য এজবিহীন নোড সর্বোচ্চ ২টি।

ইনপুট: nodes=2, edges=1

আউটপুট: গ্রাফে কোনো এজের অংশ নয় এমন নোডের সর্বোচ্চ সংখ্যা: ০

ব্যাখ্যা: কমপক্ষে ২টি নোড দরকার একটি এজ বানানোর জন্য। এই কেসে দুটোই দখল করছে। কোনো নোড বাকি নেই।

অ্যাপ্রোচ

• nodes এবং edges ভেরিয়েবলে ডেটা নেওয়া হয়।
• maximum(int nodes, int edges) ফাংশন নোড এবং এজ গ্রহণ করে এজবিহীন নোডের সর্বোচ্চ সংখ্যা রিটার্ন করে।
• i, temp, max ভেরিয়েবল নেওয়া হয়।
• for লুপ i=0 থেকে i<=nodes পর্যন্ত।
• temp = i*(i-1) হিসাব করা হয়।
• total = 2*edges হিসাব করা হয়।
• যখন temp >= total হয়, লুপ ব্রেক করা হয়।
• max = nodes - i হিসাব করা হয়।

উদাহরণ কোড

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

int maximum(int nodes, int edges) {
    int i, temp = 0, max;
    for (i = 0; i <= nodes; i++) {
        temp = i * (i - 1);
        int total = 2 * edges;
        if (temp >= total) {
            break;
        }
    }
    max = nodes - i;
    return max;
}

int main() {
    int nodes = 10;
    int edges = 5;
    cout << "Maximize number of nodes which are not part of any edge in a Graph are:" << maximum(nodes, edges) << endl;
}

আউটপুট

Maximize number of nodes which are not part of any edge in a Graph are: 6