দুটি সেট ডিজয়েন্ট সেট হয় যখন তাদের কোনো সাধারণ উপাদান নেই। অন্য কথায়, যদি দুটি সেটের ইন্টারসেকশন নিই, তবে নাল সেট পাওয়া যাবে।
পদ্ধতিটি সহজ, এই অ্যালগরিদমে দুটি সেট দেওয়া থাকে। আমরা অনুমান করি দুটি সেটই ইতিমধ্যে সর্ট করা আছে, আইটেমগুলো দুটি সেটের মধ্যে তুলনা করা হয়। যখন মিল পাওয়া যায়, তবে সেটি ডিজয়েন্ট সেট নয়, যখন কোনো আইটেম মিলে না, তবে তারা ডিজয়েন্ট সেট।
ইনপুট এবং আউটপুট
ইনপুট: দুটি সেট: set1: {15, 12, 36, 21, 14} set2: {7, 89, 56, 32} আউটপুট: উভয় সেট ডিজয়েন্টঅ্যালগরিদম
isDisjoint(set1, set2)
ইনপুট: দুটি সেট।
আউটপুট: সত্য যখন উভয় সেট ডিজয়েন্ট।
শুরু
i1 := প্রথম সেটের শুরু
i2 := দ্বিতীয় সেটের শুরু
যতক্ষণ i1 প্রথম সেটে এবং i2 দ্বিতীয় সেটে থাকে, করুন
যদি set1[i1] < set2[i2], তবে
i1 := i1 + 1
অন্যথায় যদি set2[i2] < set1[i1], তবে
i2 := i2 + 1
অন্যথায়
মিথ্যা ফেরত দিন
শেষ
সত্য ফেরত দিন
শেষউদাহরণ
#include<iostream> #include<set> using namespace std; bool isDisjoint(set<int> set1, set<int> set2) { set<int>::iterator i1, i2; i1 = set1.begin(); i2 = set2.begin(); //ইটেরেটরগুলো প্রথম এলিমেন্ট দিয়ে ইনিশিয়ালাইজ করুন while(i1 != set1.end() && i2 != set2.end()) { //যখন দুটি সেটই চেক করার জন্য কিছু এলিমেন্ট রাখে if(*i1 < *i2) i++; //যখন প্রথম সেটের আইটেম দ্বিতীয় সেটের চেয়ে কম else if(*i2 < *i1) i2++; //যখন দ্বিতীয় সেটের আইটেম প্রথম সেটের চেয়ে কম else return false; //যদি আইটেমগুলো মিলে যায়, সেটগুলো ডিজয়েন্ট নয় } return true; } int main() { set<int> set1, set2; int n1, n2; cout << "Enter number of elements in set 1: "; cin >>n1; while(n1 != set1.size()) { //ডুপ্লিকেট আইটেম বাদ পড়বে int item; cout << "Enter element: "; cin >> item; set1.insert(item); } cout << "Enter number of elements in set 2: "; cin >>n2; while(n2 != set2.size()) { int item; cout << "Enter element: "; cin >> item; set2.insert(item); } if(isDisjoint(set1, set2)) cout << "Both sets are disjoint"; else cout << "Sets are not disjoint"; }আউটপুট
Enter number of elements in set 1: 5 Enter element: 15 Enter element: 12 Enter element: 36 Enter element: 21 Enter element: 14 Enter number of elements in set 2: 4 Enter element: 7 Enter element: 89 Enter element: 56 Enter element: 32 Both sets are disjoint
