সমস্যা বিবরণ
একটি পূর্ণসংখ্যা N দেওয়া আছে যা ভার্টেক্সের সংখ্যা নির্দেশ করে। কাজ হলো N ভার্টেক্সের একটি বাইপার্টাইট গ্রাফে সর্বোচ্চ কতগুলো এজ থাকতে পারে তা বের করা।
বাইপার্টাইট গ্রাফ
- বাইপার্টাইট গ্রাফ হলো এমন গ্রাফ যাতে ২টি ভার্টেক্স সেট থাকে।
- সেটগুলো এমন যে একই সেটের ভার্টেক্স দুটি কখনো একে অপরের সাথে এজ দিয়ে সংযুক্ত থাকে না।
উদাহরণ
যদি N = 10 হয়, তবে মোট ২৫টি এজ থাকবে −
- দুটি সেটে ৫টি করে ভার্টেক্স থাকবে এবং প্রথম সেটের প্রতিটি ভার্টেক্স দূরীত সেটের প্রতিটি ভার্টেক্সের সাথে সংযুক্ত থাকবে
- অতএব মোট এজ = 5 * 5 = 25
অ্যালগরিদম
- এজ সংখ্যা সর্বোচ্চ হবে যখন একটি সেটের প্রতিটি ভার্টেক্স অন্য সেটের সব ভার্টেক্সের সাথে সংযুক্ত থাকবে অর্থাৎ edges = m * n যেখানে m এবং n হলো দুটি সেটের এজ সংখ্যা
- এজ সংখ্যা সর্বোচ্চ করার জন্য m এবং n যেন যতটা সম্ভব একে অপরের কাছাকাছি বা সমান হয়
- অতএব সর্বোচ্চ এজ সংখ্যা নিচের সূত্র দিয়ে বের করা যায় −
(n * n) / 4
উদাহরণ
#include <bits/stdc++.h> using namespace std; int getMaxEdges(int n) { return floor((n * n) / 4); } int main() { int n = 7; cout << "Maximum edges = " << getMaxEdges(n) << endl; return 0; }আউটপুট
প্রোগ্রামটি কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে −
Maximum edges = 12
