공통 원소를 가지지 않는 집합

특징

• 서로다른 집합 A,B에 대해, 집합 A와 집합 B의 교집합이 공집합이다.
• 같은 집합끼리 분리하기 위한 알고리즘으로 같은 집합은 같은 조상을 가진다.

코드(파이썬)

• 분리 집합을 구하는 과정은 2단계로 이루어진다.
  • 자식이 가장 높은 조상을 찾는 과정인 Find
  • 하나의 집합이 다른 집합의 가장 높은 조상을 가리키도록 하여 집합을 병합 하는 과정인 Union

# initialize
parent = [i for i in range(n)]
height = [0] * n

• 초기화 과정으로, 부모 인덱스를 가리키는 parent 배열과 가장 높은 부모 노드를 결정하기 위한 height 배여을 원소의 개수만큼 초기화 한다.

def find(x) :
	if x == parent[x] : return x
    parent[x] = find(parent[x])
    return parent[x]

• 현재 자식의 가장 높은 조상을 찾는 과정이다.
• 다른 조상을 가리키고 있지 않다면, 현재 본인이 가장 높은 조상이므로 본인의 인덱스를 반환한다.
• 조상이 있다면, 재귀를 통해 부모의 가장 높은 조상을 찾아 반환하도록 하여, 본인의 조상을 업데이트 한다.
• 업데이트가 완료된 조상의 인덱스를 반환하도록 한다.

def union(x, y) :
	px = find(x)
    py = find(y)
    if px == py : return
    if height[px] < height[py] : px, py = py, px
    parent[py] = px
    if height[px] == height[py] : height[py] += 1

• 두 원소를 병합하는 과정이다.
• 병합하고자 하는 원소의 가장 높은 조상을 찾아 각각 px, py에 저장한다.
• 만약 두 조상이 같다면, 이미 병합된 집합이므로 함수를 빠져나온다.
• 최적화를 위해 height 배열을 조사한다. height에 있는 값이 높을 수록 더 높은 조상이다.
• nx가 ny보다 더 높은 조상이 되도록, 두 height 값을 조사하여 필요한 경우 swap한다.
• 더 낮은 위치에 있는 조상(py)이 더 높은 위치에 있는 조상(px)을 조상으로 가르키도록 한다.
• 두 조상의 높이가 같다면 px가 py를 조상으로 가리키고 있기 때문에 py의 height를 증가시켜 준다.

#a와 b가 같은 집합에 속한다면, union 함수를 호출하여 두 집합을 병합해 준다
union(x, y)

#a와 b가 같은 집합인지 확인하고 싶다면, find 함수를 호출하여 두 원소의 가장 높은 조상을 비교한다.
if find(x) == find(y) :
	print("같은 집합")
else :
	print("다른 집합")

• 위와 같은 방법으로 두 원소를 병합하고, 같은 집합에 속하는지 여부를 확인할 수 있다.