2つの集合が互いに素（Disjoint）かどうかを判定するアルゴリズム

2つの集合に共通する要素が1つも存在しないとき、それらは互いに素（disjoint set）であるといいます。言い換えると、2つの集合の積集合（共通部分）を求めた結果が空集合になる場合、その2つの集合は互いに素です。

判定方法は非常にシンプルです。このアルゴリズムでは、2つの集合が与えられ、どちらもすでにソート済みであると仮定します。そのうえで、両方の集合の要素を先頭から順番に比較していきます。一致する要素が1つでも見つかれば互いに素ではなく、最後まで一致する要素が存在しなければ、2つの集合は互いに素であると判定できます。

入力と出力

入力：
2つの集合：
set1: {15, 12, 36, 21, 14}
set2: {7, 89, 56, 32}

出力：
Both sets are disjoint（2つの集合は互いに素である）

アルゴリズム

isDisjoint(set1, set2)

入力： 2つの集合。

出力： 2つの集合が互いに素であれば true を返します。

Begin
    i1 := 最初の集合の先頭
    i2 := 2番目の集合の先頭
    while i1 が set1 内 かつ i2 が set2 内 の間、繰り返し：
        if set1[i1] < set2[i2] ならば
            i1 := i1 + 1
        else if set2[i2] < set1[i1] ならば
            i2 := i2 + 1
        else
            return false   // 要素が一致したため互いに素ではない
    return true
End

計算量について

この手法では、各集合のポインタ（イテレータ）が常に前へ進むだけなので、計算量は O(n + m)（n、m はそれぞれの集合の要素数）となります。全要素同士を総当たりで比較する O(n × m) よりも効率的です。なお、集合が未ソートの場合は事前にソートが必要で、その場合はソートのコストが加わります。

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)
            i1++;              // 第1集合の要素が小さい場合は次へ進む
        else if(*i2 < *i1)
            i2++;              // 第2集合の要素が小さい場合は次へ進む
        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";
}

ここでは C++ の std::set を使用しています。std::set は内部で要素が常にソートされた状態で保持されるため、このアルゴリズムの前提条件（ソート済み）を自然に満たせます。また、重複する値を挿入しても自動的に1つにまとめられる点にも注意してください。

実行結果

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

この例では、set1 = {12, 14, 15, 21, 36} と set2 = {7, 32, 56, 89} の間に共通要素が存在しないため、「Both sets are disjoint（互いに素である）」と正しく判定されています。