Union Find

💡 서로소 집합 자료구조

---

합치기 찾기 자료구조. 크루스칼 알고리즘 시 사이클을 이루지 않기 위해 사용.

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

• 트리 구조로 표현

• 합집합(union), 찾기(find) 연산을 지원

  • union : x와 y가 포함되어있는 집합을 합치는 연산
  • find : x가 어떤 집합에 포함되어 있는지 찾는 연산

• 여러 개의 합치기 연산이 주어졌을 때

  1. 합집합 연산을 확인하여 서로 연결된 두 노드를 확인

     • 두 노드의 루트 노드를 각각 찾는다
     • 그 루트 노드를 부모 노드로 설정

  2. 모든 합집합 연산을 처리할때까지 1과정 반복

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
    	# 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
        parent[x] = find_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

reference