※雑に生成AIで生成したダミーデータなので叩かないで…

以下は、C++で実装されたUnion-Find（Disjoint Set Union, DSU）データ構造のコードです。グラフの連結成分を管理する際に使用され、以下の操作を効率的に行うことができます：

• 2つの要素を同じグループに統合する（union_set）
• 2つの要素が同じグループに属しているか判定する（is_connected）
• 要素の親を見つける（find_set）

主な特徴

• 経路圧縮による最適化：

  • find_set 関数でパス圧縮を行い、各要素が直接ルートに繋がるようにすることで、木の高さを抑制し、後続の検索操作を高速化します。

• ランクによる最適化：

  • union_set 関数では、ランク（ツリーの高さ）を基にして、ランクの低い木を高い木に統合します。これにより、ツリーの高さが最小限に保たれ、操作の効率が向上します。

• 親配列とランク配列の使用：

  • parent 配列は各要素の親を保持し、初期状態では各要素が自身を親としています。
  • rank 配列は各ツリーのランク（高さ）を保持し、ランクの低いツリーを高いツリーにマージする際の基準として使用します。

実行時間の計算量

• ほぼO(α(n))：
  • α はアッカーマン関数の逆関数であり、実用上はほぼ定数と見なせます。このため、各操作（find_set や union_set）は非常に高速に実行されます。

使用例

以下の main 関数では、10個の要素（0から9）を初期化し、いくつかの結合操作を行っています。is_connected 関数を使用して、特定の要素が同じセットに属しているかどうかを確認しています。

#include <iostream>
#include <vector>

class UnionFind {
private:
    std::vector<int> parent; // 各要素の親を保持
    std::vector<int> rank;   // ツリーの高さを保持

public:
    // コンストラクタ：n 個の要素を初期化
    UnionFind(int n) : parent(n), rank(n, 0) {
        for(int i = 0; i < n; ++i){
            parent[i] = i; // 各要素を自身の親に設定
        }
    }

    // 要素 x のルートを見つける（パス圧縮を適用）
    int find_set(int x) {
        if(parent[x] != x){
            parent[x] = find_set(parent[x]); // 再帰的に親を探索し、圧縮
        }
        return parent[x];
    }

    // 要素 x と y を結合する（ランクによる最適化を適用）
    void union_set(int x, int y) {
        int x_root = find_set(x);
        int y_root = find_set(y);

        if(x_root == y_root){
            return; // 既に同じセットに属している
        }

        // ランクが低い方を高い方に結合
        if(rank[x_root] < rank[y_root]){
            parent[x_root] = y_root;
        }
        else{
            parent[y_root] = x_root;
            if(rank[x_root] == rank[y_root]){
                rank[x_root]++;
            }
        }
    }

    // 同じセットに属しているかを確認
    bool is_connected(int x, int y){
        return find_set(x) == find_set(y);
    }
};

int main(){
    int n = 10; // 要素数
    UnionFind uf(n);

    // いくつかの結合操作
    uf.union_set(0, 1);
    uf.union_set(1, 2);
    uf.union_set(3, 4);

    // 接続の確認
    std::cout << "0 と 2 は同じセット: " << (uf.is_connected(0, 2) ? "はい" : "いいえ") << std::endl;
    std::cout << "0 と 3 は同じセット: " << (uf.is_connected(0, 3) ? "はい" : "いいえ") << std::endl;

    // 追加の結合
    uf.union_set(2, 3);

    std::cout << "0 と 3 を結合後:" << std::endl;
    std::cout << "0 と 3 は同じセット: " << (uf.is_connected(0, 3) ? "はい" : "いいえ") << std::endl;

    return 0;
}