서로소 집합이란 공통 원소가 없는 두 집합을 의미한다
union-find(합치기 찾기) 자료구조라고 불린다
트리 자료구조를 이용한다
- union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다
- A와 B의 루트 노드 A', B'를 각각 찾는다
- A'를 B'의 부모 노드로 설정한다(B'가 A'를 가리키도록 한다)
- 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다 (
재귀적)
(번호가 작은 원소를 부모 노드로 처리했다)
3번을 보면 3의 부모가 2의 부모여서 2의 부모인 1이 된다 (루트 노드일 때까지 재귀)
2의 부모와 3의 부모가 1으로 같기 때문에 경로 압축기법을 적용해 시간복잡도를 개선시킬 수 있다
부모 테이블값을 갱신하면 된다
😂
인생노잼