[Algorithm] Union-Find

Union-Find
:Disjoint setで使用するアルゴリズムを示します
Disjoint Set
:重複しない部分集合の要素情報を格納および操作するデータ構造
ААААААА
Union Findはツリー構造を用いて実現する.
ツリー構造を使用する理由
-タイルを使用する場合

Array[i]:i号要素が属する集合の番号(ルートノード番号)

make-set(x):Array[i]=iのように、異なる集合番号で

を初期化

union(x, y):配列内のすべての要素を巡り、yの集合番号をxの集合番号に変更します.
勘定科目の時間複雑度O(N)2479182

find(x):一度にxが属するコレクション番号を検索
時間複雑度O(1)2479182
-ツリーを使用する場合

같은 집합 = 하나의 트리 ➡️ 집합 번호 = 루트노드

make-set(x):各ノードはルートノードであるため、N個のノードを作成して自身に初期化する
時間的複雑度はO(N)よりも小さいため、find演算の時間的複雑度は2479182である.

find(x):ノードの集合番号はルートノードです.したがって、ルートノードを確認して、同じ集合であるかどうかを確認します.
АААААААААААААААА\104
平均時間複雑度は木の高さに比例するためO(logn)
Union Find操作

make-set(x)-初期化
-xを一意の要素とする新しいセット

を作成します.

union(x, y)-合
-xが属する集合とyが属する集合の合計
勘定科目xおよびyが属する2つのセットの演算

find(x)-検索
-xは、属する集合のルートノード値を返します.
どの集合に属するかを検索する演算

Union Findコード

int find(int x) {
    if(parent[x] == x) return x;

    return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return;

    parent[y] = x;

    /**
     * x와 y의 루트 노드가 같다면 같은 집합이므로 종료하고
     * 그게 아니라면 y의 부모를 x로 바꿈
     */
}

2479142=Find勘定科目のルートノードを検索する関数で、ルートノードに到達するまで親ノードに遡ります.
2479142=別のブート・ツリーとして、Union勘定科目の勘定科目xまたはyを含む部分集合を表すツリーを作成します.
リファレンス
リファレンス
リファレンス