আমাদের একটি গ্রাফ দেওয়া হয়েছে যাতে নোড এবং প্রান্ত রয়েছে৷ লক্ষ্য হল গ্রাফের যেকোনো প্রান্তের সাথে সংযুক্ত সম্ভাব্য নোডের সর্বাধিক সংখ্যা খুঁজে বের করা। আমরা জানি যে না. নোডগুলি সর্বদা একটি সম্পূর্ণ গ্রাফে প্রান্তের সংখ্যার চেয়ে কম বা সমান হবে৷
আমরা একটি সম্পূর্ণ গ্রাফ তৈরি করার চেষ্টা করে এটি করব যেখানে নোডের সংখ্যা n তারপর সেখানে n(n-1)/2 প্রান্ত থাকবে।
edge=n(n-1)/2 (এখানে নোডের জন্য n)
2*edge=n(n-1)। একবার n(n-1)> না। প্রান্ত তারপর আমরা অতিরিক্ত নোড আছে. তাই i=1 থেকে i=n পর্যন্ত পুনরাবৃত্তি করুন।
i(i-1)>2* প্রান্ত পর্যন্ত। ফলাফল হিসাবে n-i ফেরত দিন।
উদাহরণ দিয়ে বোঝা যাক −
ইনপুট − নোড=5, প্রান্ত=2
আউটপুট − গ্রাফের কোন প্রান্তের অংশ নয় এমন নোডের সংখ্যা সর্বাধিক করুন − 2
ব্যাখ্যা −
2টি প্রান্তে সর্বনিম্ন 3টি নোড এবং সর্বোচ্চ 4টি নোড থাকতে পারে৷
3টি নোডের জন্য সর্বাধিক বাম নোড কোন প্রান্ত ছাড়াই=2
ইনপুট − নোড=2, প্রান্ত=1
আউটপুট − গ্রাফের কোন প্রান্তের অংশ নয় এমন নোডের সংখ্যা সর্বাধিক করুন − 0
ব্যাখ্যা −
একটি প্রান্ত তৈরি করতে কমপক্ষে 2টি নোড প্রয়োজন। এক্ষেত্রে উভয়ই দখলদার। কোনো নোড বাকি নেই৷
৷নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
-
আমরা উপলব্ধ ডেটার জন্য দুটি পরিবর্তনশীল নোড এবং প্রান্ত নিই৷
-
ফাংশন সর্বাধিক (int নোড, int প্রান্ত) কোন লাগে. নোড এবং প্রান্তের প্যারামিটার হিসাবে এবং সর্বাধিক নোডের গণনা প্রদান করে যা একটি গ্রাফের কোন প্রান্তের অংশ নয়
-
ভেরিয়েবল i, temp এবং max নিন।
-
স্টার্ট লুপ FOR i=0 থেকে i<=nodes
পর্যন্ত -
temp=i*(i-1)
গণনা করুন -
2* প্রান্ত
হিসাবে পরিবর্তনশীল মোট গণনা করুন -
যখনই তাপমাত্রা মোটের চেয়ে বেশি হয়ে যায়, FOR
ভাঙুন -
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
