Union-Find (서로소 집합)

1. 주요 연산

find(x)

• x가 속한 집합의 대표 노드를 반환해요.

• *경로 압축(Path Compression)**을 사용하면, 트리 구조가 납작해져서 성능이 좋아져요.

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

union(x, y)

• x와 y가 속한 집합을 하나의 집합으로 합쳐요.

• 루트를 기준으로 병합하며, 효율을 위해 랭크(rank) 또는 크기(size)를 고려하기도 해요.

void union(int[] parent, int x, int y) {
    int px = find(parent, x);
    int py = find(parent, y);
    if (px != py) {
        parent[py] = px; // py의 루트를 px로 병합
    }
}

2. 초기화

• 각 원소는 자기 자신이 루트로 시작해요.

int[] parent = new int[n + 1];
for (int i = 0; i <= n; i++) {
    parent[i] = i;
}

3. 사용 예시

네트워크 연결 여부 확인

if (find(a) == find(b)) {
    // 같은 집합에 속해 있음 (연결되어 있음)
}

4. 시간 복잡도

• 암묵적인 경로 압축 + union by rank/size를 사용할 경우

• 거의 O(1)에 가까운 성능 (정확히는 O(α(N)), 역 아커만 함수)

5. 비유로 이해하기

• 각각의 사람(노드)은 조장을 가리키고 있음

• find()는 궁극적으로 조장이 누군지 알아내는 과정

• union()은 두 반을 합쳐서 같은 조장을 갖게 만드는 과정