[JS] 유니온 파인드 (Union-Find)

❗️ 유니온 파인드 (Union-Find)

• 그래프 알고리즘으로 서로소 집합 알고리즘이라고도 불림
• 그래프 위의 두 개의 노드를 선택해서 해당 노드들이 같은 그래프에 속하는지 판별

✅ 구현 방식

1. 초기화 : 각 노드가 각각의 집합에 포함되도록 초기화
2. Find : 특정 노드의 부모를 찾음 (해당 노드가 속한 집합의 루트를 반환)
3. Union : 두 노드 A,B를 한쪽으로 합침

✅ 코드 구현

let parent = Array(N+1).fill(-1)

function union(x, y) {
  x = find(x);
  y = find(y);
  if (x != y) {
    parent[x] = y;
  }
}

function find(x) {
  if (parent[x] < 0) return x;
  parent[x] = find(parent[x]);
  return parent[x];
}