আমাদের নোডের সংখ্যা (Nov) এবং এজের সংখ্যা (Noe) দেওয়া আছে। লক্ষ্য হলো এমন গ্রাফে সর্বনিম্ন ও সর্বোচ্চ কতগুলো আইসোলেটেড ভার্টেক্স (যে ভার্টেক্সের কোনো এজ নেই) থাকতে পারে তা বের করা।
ন্যূনতম আইসোলেটেড ভার্টেক্স
প্রতিটি এজ আলাদা ২টি ভার্টেক্স ব্যবহার করে (কমন ভার্টেক্স নেই)। তাই নন-আইসোলেটেড ভার্টেক্স = 2 * Noe। আইসোলেটেড = Nov - 2*Noe। যদি Nov <= 2*Noe হয় তবে সব ভার্টেক্সের এজ থাকে, আইসোলেটেড = ০।
সর্বোচ্চ আইসোলেটেড ভার্টেক্স
এজগুলো কমপ্লিট গ্রাফ (পলিগন) বানায়ে minimum ভার্টেক্সে ফিট করাতে হবে। n-সাইডেড পলিগনে ডায়াগোনালের সংখ্যা n(n-3)/2, টোটাল এজ = n(n-1)/2। এই ফর্মুলা দিয়ে minimum ভার্টেক্স বের করে বাকি আইসোলেটেড হবে।
ইনপুট
No. of vertices 5, edges 6
আউটপুট
Minimum isolated vertices 0. Maximum isolated vertices 1.
ইনপুট
no. of vertices 2, edges=1
আউটপুট
Minimum isolated vertices 0. Maximum isolated vertices 0.
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- noe এবং nov ইন্টিজার।
- findisolatedvertices(int v, int e) ফাংশন প্রিন্ট করে।
- v <= 2*e হলে minimum ০, অন্যথায় v - 2*e।
- সর্বোচ্চ জন্য i=1 থেকে v পর্যন্ত লুপে i*(i-1)/2 >= e হলে ব্রেক। i ভার্টেক্সে e এজ ফিট হয়। সর্বোচ্চ আইসোলেটেড = v - i।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
void findisolatedvertices(int v, int e){
if (v <= 2 * e)
cout << "Minimum no. of isolated vertices: " << 0 << endl;
else {
int niso = 2*e;
cout << "Minimum no. of isolated vertices: " << v - niso << endl;
}
int i;
for (i = 1; i <= v; i++) {
if (i * (i - 1) / 2 >= e)
break;
}
cout << endl << "Maximum no. of isolated vertices: " << v-i;
}
int main(){
int nov = 5;
int noe = 2;
findisolatedvertices(nov, noe);
return 0;
}আউটপুট
Minimum no. of isolated vertices: 1 Maximum no. of isolated vertices: 2
