[알고리즘] Union-Find

Union-Find

• 분리 집합을 표현하기 위해 사용하는 알고리즘
• 트리 구조를 이용해 구현된다.
• 무방향 그래프에서의 사이클 생성 여부를 판별할 수 있다.

Union

void unionParent(int x, int y) {
    int px = findParent(x);
    int py = findParent(y);
    if (px <= py)
        parent[py] = px;
    else
        parent[px] = py;
}

Find

int findParent(int x) {
    if (parent[x] == x)
        return x;
    parent[x] = findParent(parent[x]);    //경로 압축
    return parent[x];
}