检查两个给定的集合是否不相交?

当两个集合没有公共元素时,它们是不相交的集合。换句话说,如果我们得到两个集合的交集,那么我们将得到空集合。

该方法很简单,该算法给出了两组。我们假设两个集合都已排序,并且在两个集合之间比较了项目。当存在匹配项时,它不是不相交集,当没有项目匹配时,它们就是不相交集。

输入输出

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

以上是 检查两个给定的集合是否不相交? 的全部内容, 来源链接: utcz.com/z/322422.html

回到顶部