UnionFind는 원소들이 서로소 집합으로 나눠져 있을때 같은 집합으로 확인하고 합치는 작업을 효율적으로 처리한다.

요약

본문

• union find는 disjoint set Union => DSU
  • Disjoint set: 서로소 집합
  • Disjoint Set Union: 서로소 집합을 하나로 합치는 로직
• 두가지 인터페이스를 갖는다.
  • find(x): x가 속한 집합의 대표 찾기
    • 각 원소는 부모 포인터를 갖고 트리처럼 연결되어 있음
    • 루트가 그 집합의 대표
  • union(a,b): a가 속한 집합과 b가 속한 집합 합치기
• 언제 쓰는가?
  • 그래프에서 연결요소 관리
  • 사이클 판별(무방향 그래프에서 union 하다가 같은 루트이면 사이클 )
  • 크루스칼 MST(간선 오름차순으로 union, 이미 연결이면 스킵)
  • 같은 그룹 관계를 계속 합치고 질의 할때

참고