जांचें कि दो दिए गए समुच्चय असंयुक्त हैं या नहीं

परिचय

दो समुच्चय असंयुक्त समुच्चय होते हैं जब उनका कोई सामान्य तत्व नहीं होता। दूसरे शब्दों में, यदि हम दो समुच्चयों का प्रतिच्छेदन प्राप्त करते हैं, तो हमें रिक्त समुच्चय मिलेगा।

विधि सरल है, इस एल्गोरिदम में, दो समुच्चय दिए गए हैं। हम मान लेते हैं कि दोनों समुच्चय पहले से क्रमबद्ध हैं, आइटम्स की तुलना दो समुच्चयों के बीच की जाती है। जब कोई मेल होता है, तो यह असंयुक्त समुच्चय नहीं है, जब कोई आइटम मेल नहीं खाता, तो वे असंयुक्त समुच्चय हैं।

इनपुट और आउटपुट

इनपुट: दो समुच्चय: set1: {15, 12, 36, 21, 14} set2: {7, 89, 56, 32}
आउटपुट: दोनों समुच्चय असंयुक्त हैं

एल्गोरिदम

isDisjoint(set1, set2)
इनपुट: दो समुच्चय
आउटपुट: सत्य जब दोनों समुच्चय असंयुक्त हों

Begin
    i1 := पहले समुच्चय की शुरुआत
    i2 := दूसरे समुच्चय की शुरुआत
    जब तक i1 पहले समुच्चय में और i2 दूसरे समुच्चय में, करें
        यदि set1[i1] < set2[i2], तो
            i1 := i1 + 1
        अन्यथा यदि set2[i2] < set1[i1], तो
            i2 := i2 + 1
        अन्यथा
            असत्य लौटाएं
    done
    सत्य लौटाएं
End

उदाहरण (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(); // पहले तत्व के साथ पुनरावर्तक आरंभ करें
    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