[알고리즘] union-find

const nodes = 6
const testEdges = [
  [1, 4],
  [2, 3],
  [2, 4],
  [5, 6],
]

const findParent = (parent, x) => {
  if (parent[x] != x) {
    parent[x] = findParent(parent, parent[x])
  }
  return parent[x]
}

const unionParent = (parent, a, b) => {
  a = findParent(parent, a)
  b = findParent(parent, b)
  if (a < b) {
    parent[b] = a
  } else {
    parent[a] = b
  }
}

const parent = Array.from({ length: nodes + 1 }, (_, i) => i)

for (const [node1, node2] of testEdges) {
  unionParent(parent, node1, node2)
}

parent 배열에는 해당 인덱스 노드의 루트인 노드번호가 존재.

이를 활용해서 합집합을 구현할 수도 있고, 트리에서 특정 노드의 루트를 찾아서 사이클의 존재유무를 판단하는 데 사용할 수도 있다.

최소 신장트리 MST(Minumum Spanning Tree) 알고리즘 중 하나인 Kruskal's Algorithm을 구현할 때 간선 선택 시, union-find를 사용하여 사이클을 판명한다.