Union-Find

📌서로소 집합 (Disjoint-Set)

• 서로소 집합 (Disjoint-set)
• 서로 중복 포함된 원소가 없는 집합들. 교집합이 없는 집합들
• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. = 대표자
• 서로소 집합을 표현 하는 방법
  • 연결 리스트
  • 트리

💡서로소 집합 (연결리스트)

• 같은 집합의 원소들은 하나의 연결리스트로 관리
• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
• 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.
• union(e,f) = e가 속한 집합에 f가 속한 집합이 흡수된다!

💡서로소 집합 (트리)

• 하나의 집합을 하나의 트리로 표현한다.
• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.
  
  

• 연결리스트를 구현하는것은 번거롭기 때문에 자신의 집합에 속해있는 부모의 관계를 이용해 배열로 만든다.
• 부모를 가리키는 집합이기 때문에 보통 parents라고 명명한다.

📌UnionFind 알고리즘

💡서로소 집합 연산

• Make-Set(x)
  • 가장 작은 단위의 단위 집합을 만드는 연산
  • 원소 모두 각각 개별의 집합을 만들고 시작한다.
• Find-Set(x)
  • 대표자를 찾는 연산
• Union(x,y)
  • x가 속한 집합과 y가 속한 집합을 합치는 연산

💡연산의 효율을 높이는 방법

• Rank을 이용한 Union
  • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크라는 이름으로 저장한다.
  • 두 집합을 합칠 때 랭크가 낮은 집합을 높은 집합에 붙인다.
• Path compression
  • Find-set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾼다.
  • Find-set을 행할 때 일어나기 때문에 Find-set을 하기 전까지는 바뀌지 않는다.