[자료구조] 분리 집합 (Union-Find)

그래프 이론

 

[자료구조 소개]

그래프의 노드끼리의 합집합에 대한 정보를 저장하는 자료구조. 서로소 집합(Disjoint Set)이라고도 함

 

---

[자료구조 특징]

• 재귀 사용
• 재귀를 사용하므로 최적화 필요 → 경로 압축
• Union by Size, Union by Rank와 같은 최적화 방법도 존재
• Union by Size를 사용하여 집합의 크기를 알 수 있음

---

[코딩 방법 / 일반적인 방법]

 

[초기화]

1. 사이즈가 N인 배열 생성, arr[i] = i로 초기화

[Find]

1. parent[cur] != cur인 경우, parent[cur] = Find(parent[cur]) (경로 압축) 후 return parent[cur]
2. parent[cur] == cur인 경우, return cur

[Union]

1. Union하는 두 원소 u, v에 대해 pu = Find(u), pv = Find(v)를 이용하여 pu, pv 저장
2. pu == pv면 return
3. pu < pv면 parent[pv] = pu 아니면 parent[pu] = pv

---

[코딩 방법 / Union by Size]

 

[초기화]

사이즈가 N인 배열 생성, arr[i] = -1로 초기화

 

[Find]

1. parent[cur] >= 0인 경우, parent[cur] = Find(parent[cur]) (경로 압축) 후 return parent[cur]
2. parent[cur] < 0인 경우, return cur

[Union]

1. Union하는 두 원소 u, v에 대해 pu = Find(u), pv = Find(v)를 이용하여 pu, pv 저장
2. pu == pv면 return
3. -parent[pu] < -parent[pv]면 parent[pv] += parent[pu], parent[pu] = pv 아니면 parent[pu] += parent[pv], parent[pv] = pu

---

[시간 복잡도]

Union: $O(\alpha(n))$

Find: $O(\alpha(n))$

 

---

[응용]

• 무향 그래프의 사이클 검출
• Kruskal 알고리즘에서 사용: kangwlgns.tistory.com/52

---

[공부용 링크]

blog.naver.com/ndb796/221230967614