유니온 파인드 (Union-Find)

각 노드가 서로 연결되어 있는지 확인하기 위해 활용되는 알고리즘.

노드끼리 연결되어 있는지 확인만 하고 싶다면,

다음과 같이 바꿔도 연결 여부를 알 수 있다.

바뀐 그래프는 각 노드의 최상단 부모 노드와 연결하는 방식으로 보다 간단하게 표현한다.

이 때, 각 부모 노드를 찾고 이를 합치는 과정에 Union 과 find 가 수행되어 Union-find 라 칭한다.

예시 코드

// 해당 배열에서 x 에 대한 최상위 부모 노드 값을 리턴
private int find(int[] parent, int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent, parent[x]);
}

// 해당 배열에서 x, y 가 연결될 수 있도록 합침
private void union(int[] parent, int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);

    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}