How to check if two given sets are disjoint in C++

In this tutorial, we are going to learn how to check if two sets are disjoint in C++. Two sets are disjoint if the sets do not have any common elements.

Naive Approach

Let us consider two arrays of sizes n and m. For each element in the first set, we should iterate through the second set and if we find an element in the second set which is equal to the element in the first set then we can say that the sets are not disjoint sets.

Implementation:

#include <bits/stdc++.h>
using namespace std;
bool isDisjoint(int a[],int b[],int n,int m){
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(a[i] == b[j]){
                return false;
            }
        }
    }
    return true;
}
int main(){
    int n,m,i,j;
    cout<<"Enter the size of the first set"<<endl;
    cin>>n;
    cout<<"Enter the elements of the first set"<<endl;
    int a[n];
    for(i = 0;i < n;i++){
        cin>>a[i];
    }
    cout<<"Enter the size of the second set"<<endl;
    cin>>m;
    cout<<"Enter the elements of the second set"<<endl;
    int b[m];
    for(i = 0;i < m;i++){
        cin>>b[i];
    }
    if(isDisjoint(a,b,n,m)){
        cout<<"The sets are disjoint"<<endl;
    }
    else{
        cout<<"The sets are not disjoint"<<endl;
    }
}

Output:

Enter the size of the first set
3
Enter the elements of the first set
1 2 3
Enter the size of the second set
4
Enter the elements of the second set
4 5 6 7
The sets are disjoint

In the above code, the isDisjoint() function takes the two sets and their sizes as arguments and returns true if the sets are disjoint sets or else it returns false if they are not disjoint sets.

Time Complexity: O(n*m)

Optimal Approach:

We can use the hashing technique to check if two sets are disjoint sets. At first, we should insert all the elements of the first set into a hash table. Now we should iterate through each element of the second set and check if that element already exists in the hash table. If an element from the second set is already present in the hash table then we can say that the sets are not disjoint sets.

Implementation:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,i,j;
    cout<<"Enter the size of the first set"<<endl;
    cin>>n;
    cout<<"Enter the elements of the first set"<<endl;
    int a[n];
    for(i = 0;i < n;i++){
        cin>>a[i];
    }
    cout<<"Enter the size of the second set"<<endl;
    cin>>m;
    cout<<"Enter the elements of the second set"<<endl;
    int b[m];
    for(i = 0;i < m;i++){
        cin>>b[i];
    }
    unordered_map<int,bool> u;
    // Adding elements of first set into unordered map
    for(i = 0;i < n;i++){
        u[a[i]] = true;
    }
    bool flag = true;
    for(i = 0;i < m;i++){
        /* The find method returns a pointer to the
           end of the unordered map if the element
           doesnot exist */
        if(u.find(b[i]) != u.end()){
            flag = false;
            break;
        }
    }
    if(flag){
        cout<<"The sets are disjoint"<<endl;
    }
    else{
        cout<<"The sets are not disjoint"<<endl;
    }
}

 

Output:

Enter the size of the first set
3
Enter the elements of the first set
1 2 3
Enter the size of the second set
4
Enter the elements of the second set
3 4 5 6
The sets are not disjoint

An unordered_map in C++ works like a hash table. On average the time complexity for search and insert in unordered_map is O(1).

In an unordered_map, we can use the find() function to search for a key. An iterator pointing to the element is returned by the find() function if the key exists in the unordered_map or else an iterator pointing to the end of the unordered_map is returned if the key does not exist.

So while searching for the elements of the second set in the hash table, if the find() function returns an iterator which is not equal to the iterator pointing to the end of the unordered_map then we can say that the two sets are not disjoint sets.

Time Complexity: O(n+m)

We hope that you have got a clear idea of how to check if two sets are disjoint in C++.

Also read: Check if a key is present in a C++ map

Leave a Reply

Your email address will not be published. Required fields are marked *