Union & Find

Union & Find

static void union(int a, int b) {
    int aRoot = find(a);
    int bRoot = find(b);

    parent[bRoot] = aRoot; //b는 자기자신을 가리키다가 a를 가리키게 된다
}

static int find(int a) {
    if(parent[a]==a) {
        return a;
    }
    else {
        parent[a] = find(parent[a]);
        return parent[a];
    }
}

네트워크연결문제가 이걸 이용한 것.

 parent[a] = find(parent[a]);

이걸로 인해 탐색성능이 향상된다. 

하나씩 타고가는게 아니라 모든 하위노드들이 바로 Root에 연결된다.

찾는 과정에서 연결해줌.