← 22주차 · 유니온 파인드와 MST
보통유니온 파인드

유니온 파인드 구현

원소 수 n과 연산 목록 operations가 주어져요. 원소는 0번부터 n-1번까지 있고, 처음엔 저마다 혼자예요. 각 연산은 [종류, a, b] 형태예요.

종류가 0이면 합치기로, a가 속한 무리와 b가 속한 무리를 하나로 합쳐요. 종류가 1이면 묻기로, a와 b가 지금 같은 무리인지 확인해요. 묻기 연산의 답(true/false)을 순서대로 담은 배열을 반환해요.

각 원소가 자기 대표를 가리키게 하고, 대표를 찾을 때 거쳐 온 원소들을 대표에 바로 붙이면(경로 압축) 연산이 거의 상수 시간에 가까워져요.

예시

예시 1
입력
n = 4, operations = [[0, 0, 1], [1, 0, 1], [1, 0, 2], [0, 2, 3], [1, 2, 3]]
출력
[true, false, true]
설명
0·1을 합친 뒤 0·1은 같은 무리(true), 0·2는 다른 무리(false), 2·3을 합친 뒤 2·3은 같은 무리(true)예요.
예시 2
입력
n = 3, operations = [[1, 0, 2]]
출력
[false]
설명
아무것도 합치지 않았으니 0과 2는 다른 무리예요.

제한 사항

  • 1 ≤ n ≤ 100,000
  • 1 ≤ operations.length ≤ 200,000
  • 종류는 0 또는 1이고, 0 ≤ a, b < n이에요.
parent 배열을 자기 자신으로 초기화해요. find(x)는 대표를 찾으며 경로를 압축하고, union은 두 대표를 잇되 작은 무리를 큰 무리 밑에 붙여요. 묻기 연산은 find(a) === find(b)의 결과를 결과 배열에 담아요.
javascript
function unionFind(n, operations) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const size = new Array(n).fill(1);
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  function union(a, b) {
    let ra = find(a);
    let rb = find(b);
    if (ra === rb) return;
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra;
    size[ra] += size[rb];
  }
  const result = [];
  for (const [kind, a, b] of operations) {
    if (kind === 0) union(a, b);
    else result.push(find(a) === find(b));
  }
  return result;
}
이전 문제모든 쌍 최단 거리
다음 문제그래프 사이클 판정
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.