이론

Union-Find(Disjoint Set)은 그래프를 표현할 수 있는 굉장히 직관적인 알고리즘이다.

각 트리를 루트 노드를 가르키는 상호 배타적 집합 (즉 공통 원소가 없어야 함)으로 간주하고 find, union 연산만으로 연결성을 확인한다.

기본 전제

1. 모든 노드는 해당 노드의 부모 노드를 가리킨다. parent[v] = u
2. 부모 노드가 없는 경우는 자기 자신을 가리킨다 == 루트 노드 parent[v] = v

find

find 는 해당 노드의 루트 노드를 찾는 연산이다. 전제에 따르면 루트 노드를 제외한 모든 노드들이 부모를 가르킨다. 따라서 parent[v]==v 일때까지 재귀적으로 해당 노드의 부모를 리턴한다면 루트 노드에 도달한다.

const find = (v) => {
	if (parent[v] !== v) {
		return find(parent[v])
	}
	return v
}

union

union 은 두 원소의 집합(==트리)을 합치는 연산이다. 두 집합의 루트를 찾은 후 한 집합의 부모 노드를 다른 집합의 루트 노드로 바꾸면 된다.

const union = (v, u) => {
  const root1 = find(v)
  const root2 = find(u)
	if (root1 !== root2){
		parent[root2] = root1
	}
}

기본 골조는 위와 같다. 그러나 각 연산에서 최적화를 위해 수정해야할 부분 있다.

find 최적화

유니온 파인드 자료구조는 각 원소의 루트 노드만 알면 된다. 때문에 find 연산을 수행할 때 부모를 계속 찾아 간다면 비효율이 발생한다. 만약 아래처럼 tree가 치우친다면 find 연산을 수행할 때마다 O(N)의 시간 복잡도가 발생한다.