두 세트는 공통 요소가 없을 때 분리된 세트입니다. 즉, 두 집합의 교집합을 얻으면 null 집합이 됩니다.
방법은 간단합니다. 이 알고리즘에서는 두 세트가 제공됩니다. 두 세트가 이미 정렬되어 있다고 가정하고 두 세트 간에 항목을 비교합니다. 일치하는 항목이 있으면 disjoint 집합이 아니고 일치하는 항목이 없으면 disjoint 집합입니다.
입력 및 출력
Input: Two sets: set1: {15, 12, 36, 21, 14} set2: {7, 89, 56, 32} Output: Both sets are disjoint
알고리즘
isDisjoint(set1, set2)
입력 :2세트입니다.
출력: 두 집합이 서로 연결되지 않은 경우 참입니다.
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