Union Find(連結セットの検索)

Union Find(Union Find)は典型的なグラフィック理論アルゴリズムである.「集合」(Disjoint)集合アルゴリズムとも呼ばれます.複数のノードが存在する場合、現在の2つのノードが同一のグラフィックに属しているか否かを2つのノードを選択することによって判別するアルゴリズム.アレイによりUnion-Findを実装できます.

しょきじょうたい

複数のノードが互いに自由に存在する場合、すべてのノードが互いに接続されず、それぞれが集合内の要素としてのみ使用される場合、すべての値は自分を指します.すなわち,Parent配列のインデックスはノード番号を表し,配列の値は「親ノード番号」を表す.
Parent[idx] = idx;

せつぞく

2つのノードを接続すると、1つの値が別の値を親ノードにします.
例えば、1つのノードが2つのノードに接続されている場合、Parent 1[1]=1、Parent[2]=1となる.
ここで2と3が接続されている場合、Parent[3]=2;例外の場合、2は最上位の親ノードではないので、再帰関数Parent[3]=Parent[2]...つまり、Parent[3]=1です.

Find

再帰関数を実行することで、これら2つの数がParent[3]=2->Parent[2]=1のようにParent[idx]=idxになるまで、同じ親の下にあることを確認できます.
最上位の親ノードの番号を取得します.

コードC++

#include <iostream>
#include <vector>
#define MAX_NODE 100

using namespace::std;

int n; // 노드의 개수

vector<int> Parent(MAX_NODE);

// 유니온 -파인드 사용을 위해 Parent[idx] = idx 로 초기 상태 설정
void Union_init(){
    for (int i = 0; i < n; i++) {
        Parent[i] = i;
    }
}

// 부모노드를 찾는 함수
int getParent(int x){
    if (Parent[x] == x) {
        return x;
    }
    
    return Parent[x] = getParent(Parent[x]);
}

// 두 부모 노드를 합치는 함수
void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if (a < b) {
        Parent[b] = a;
    }
    else{
        Parent[a] = b;
    }
}

// 같은 부모를 가지는지 확인
bool findParent(int a, int b){
    if (getParent(a) == getParent(b)) {
        return true;
    }
    
    return false;
}