Kiểm tra hai tập hợp có rời nhau không

Giới thiệu

Hai tập hợp là tập rời nhau khi chúng không có phần tử chung. Nói cách khác, nếu ta lấy giao của hai tập hợp, ta sẽ được tập rỗng.

Phương pháp đơn giản: trong thuật toán này, cho hai tập hợp. Ta giả định cả hai tập hợp đã được sắp xếp, các phần tử được so sánh giữa hai tập hợp. Khi có sự trùng khớp, thì đó không phải tập rời nhau, khi không có phần tử nào trùng khớp, chúng là tập rời nhau.

Đầu vào và Đầu ra

Đầu vào: Hai tập hợp: set1: {15, 12, 36, 21, 14} set2: {7, 89, 56, 32}
Đầu ra: Cả hai tập hợp đều rời nhau

Thuật toán

isDisjoint(set1, set2)
Đầu vào: Hai tập hợp.
Đầu ra: True khi cả hai tập hợp rời nhau.

Begin
    i1 := đầu của tập hợp thứ nhất
    i2 := đầu của tập hợp thứ hai
    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

Ví dụ (C++)

#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();  // khởi tạo iterator với phần tử đầu
    while(i1 != set1.end() && i2 != set2.end()) {
        // khi cả hai tập còn phần tử để kiểm tra
        if(*i1 < *i2)
            i1++;  // khi phần tử tập thứ nhất nhỏ hơn tập thứ hai
        else if(*i2 < *i1)
            i2++;  // khi phần tử tập thứ hai nhỏ hơn tập thứ nhất
        else
            return false;  // nếu phần tử trùng khớp, tập không rời nhau
    }
    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()) {
        // các phần tử trùng sẽ bị loại
        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";
}

Kết quả

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