ตรวจสอบว่าชุดที่ให้มาสองชุดไม่ปะติดปะต่อกันหรือไม่?

สองชุดเป็นชุดที่ไม่ปะติดปะต่อเมื่อไม่มีองค์ประกอบร่วมกัน กล่าวอีกนัยหนึ่ง หากเราได้จุดตัดของสองเซต เราก็จะได้เซตว่าง

วิธีการนั้นง่าย ในอัลกอริธึมนี้ ให้สองชุด เราคิดว่าทั้งสองชุดได้รับการจัดเรียงแล้ว รายการจะถูกเปรียบเทียบระหว่างสองชุด เมื่อมีการจับคู่ก็จะไม่ใช่ชุดที่ไม่ปะติดปะต่อกัน เมื่อไม่มีรายการใดที่ตรงกัน จะเป็นชุดที่ไม่ปะติดปะต่อกัน

อินพุตและเอาต์พุต

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