ตรวจสอบว่าชุด (Set) สองชุดเป็น Disjoint Sets หรือไม่

บทนำ

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

วิธีการง่ายๆ: ในอัลกอริทึมนี้ กำหนดเซตสองชุด สมมติว่าทั้งสองเซตเรียงลำดับแล้ว เปรียบเทียบรายการระหว่างสองเซต เมื่อมีการ match แสดงว่าไม่ใช่ Disjoint Sets เมื่อไม่มีรายการตรงกันเลย คือ Disjoint Sets

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

Input: เซตสองชุด: set1: {15, 12, 36, 21, 14} set2: {7, 89, 56, 32}
Output: เซตทั้งสองเป็น Disjoint Sets

อัลกอริทึม

isDisjoint(set1, set2)
Input: เซตสองชุด
Output: True เมื่อทั้งสองเซตเป็น Disjoint

Begin
    i1 := เริ่มต้นของเซตแรก
    i2 := เริ่มต้นของเซตที่สอง
    while i1 ใน set1 และ i2 ใน set2, 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

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <set>
using namespace std;

bool isDisjoint(set set1, set set2) {
    set::iterator i1, i2;
    i1 = set1.begin(); i2 = set2.begin();
    // initialize iterators กับอิลิเมนต์แรก
    while (i1 != set1.end() && i2 != set2.end()) {
        // เมื่อทั้งสองเซทยังมีอิลิเมนต์ให้ตรวจสอบ
        if (*i1 < *i2)
            i1++;  // เมื่อไอเทมของเซตแรกน้อยกว่าเซตที่สอง
        else if (*i2 < *i1)
            i2++;  // เมื่อไอเทมของเซตที่สองน้อยกว่าเซตแรก
        else
            return false;  // ถ้าไอเทมตรงกัน เซตไม่ใช่ disjoint
    }
    return true;
}

int main() {
    set 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