দুটি প্রদত্ত সেট বিচ্ছিন্ন কিনা তা পরীক্ষা করে দেখুন?

কোন সাধারণ উপাদান না থাকলে দুটি সেট ডিসজয়েন্ট সেট হয়। অন্য কথায়, যদি আমরা দুটি সেটের ছেদ পাই, তাহলে আমরা নাল সেট পাব।

পদ্ধতিটি সহজ, এই অ্যালগরিদমে দুটি সেট দেওয়া আছে। আমরা অনুমান করি যে উভয় সেট ইতিমধ্যেই সাজানো হয়েছে, আইটেম দুটি সেটের মধ্যে তুলনা করা হয়। যখন একটি মিল থাকে, তখন এটি একটি বিচ্ছিন্ন সেট নয়, যখন কোনো আইটেম মেলে না, সেগুলি বিচ্ছিন্ন সেট হয়৷

ইনপুট এবং আউটপুট

Input:
Two sets:
set1: {15, 12, 36, 21, 14}
set2: {7, 89, 56, 32}
Output:
Both sets are disjoint

অ্যালগরিদম

isDisjoint(set1, set2)

ইনপুট :দুই সেট।

আউটপুট: সত্য যখন উভয় সেট বিচ্ছিন্ন হয়।

Begin
   i1 := start of first set
   i2 := start of second set
   while i1 in set1 and i2 in set 2, do
      if set1[i1] < set2[i2], then
         i1 := i1 + 1
      else if set2[i2] < set1[i1], then
         i2 := i2 + 1
      else
         return false
   done
   return true
End

উদাহরণ

#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();            //initialize iterators with first element
   while(i1 != set1.end() && i2 != set2.end()) {         //when both set have some elements to check
      if(*i1 < *i2)
         i1++;                   //when item of first set is less than second set
      else if(*i2 < *i1)
         i2++;               //when item of second set is less than first set
      else
         return false;            //if items are matched, sets are not disjoint
   }
   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()) {       //duplicate items will be discarded
      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