Union-Find 알고리즘 정리

[voidmatcha]

핵심 개념

• 각 노드의 인덱스의 값을 부모 노드의 인덱스로 저장
• 최상위 노드의 경우 자기 자신의 인덱스를 저장

MST인지를 판별하거나 사이클을 판단하는데 사용할 수 있음

핵심 연산

• unionParent: 서로 다른 두 트리를 합치는 연산
• findParent: 최상위 노드를 찾는 연산

시간복잡도 및 공간복잡도 최적화

WIP
참고 1: https://github.com/im-d-team/Dev-Docs/blob/20210117/Dae-Hwa/CS/union-find.md
참고 2: https://www.notion.so/Union-Find-Disjoint-Set-821e76d39f8f43f7af5763853c7162e7

Union-Find를 이용해 풀 수 있는 문제

• 섬 연결하기
• 네트워크 연결