সমস্যা বিবৃতি
একটি পূর্ণসংখ্যা N দেওয়া হয়েছে যা শীর্ষবিন্দুর সংখ্যাকে প্রতিনিধিত্ব করে। কাজটি হল N শীর্ষবিন্দুর দ্বিপক্ষীয় গ্রাফে সম্ভাব্য সর্বাধিক সংখ্যক প্রান্ত খুঁজে বের করা।
দ্বিপক্ষীয় গ্রাফ
- একটি দ্বিপক্ষীয় গ্রাফ হল এমন একটি যার 2 সেট শীর্ষবিন্দু রয়েছে।
- সেটটি এমন যে একই সেটের শীর্ষবিন্দুগুলি কখনই তাদের মধ্যে একটি প্রান্ত ভাগ করবে না৷
উদাহরণ
যদি N =10 হয় তাহলে মোট 25টি প্রান্ত হবে −
- উভয় সেটেই 5টি শীর্ষবিন্দু থাকবে এবং প্রথম সেটের প্রতিটি শীর্ষবিন্দুতে দ্বিতীয় সেটের প্রতিটি শীর্ষবিন্দুর একটি প্রান্ত থাকবে
- অতএব মোট প্রান্ত হবে 5 * 5 =25
অ্যালগরিদম
- প্রদত্ত সেটের প্রতিটি শীর্ষে অন্য সেটের প্রতিটি শীর্ষবিন্দুর একটি প্রান্ত থাকলে প্রান্তের সংখ্যা সর্বাধিক হবে যেমন প্রান্ত =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
