그룹을 지을 때 사용할 수 있는 알고리즘이다. 처음에 자기 자신을 부모로 설정하고 조건에 따라 부모를 설정한다. Find는 자신의 최상위 부모를 찾는 역할을 한다. Union은 두 변수의 부모가 다르다면 하나의 최상위 부모를 다른 하나의 최상위 부모의 자식으로 만들어 두개의 그룹이 합쳐지는 기능을 수행한다.
parent = [x for x in range(10)] # 자기 자신이 부모로 초기화
def find_parent(x, parent):
if parent[x] == x: # x가 최상위 부모
return x
#x의 부모중 최상위 부모 찾기
parent[x] = find_parent(parent[x], parent)
return parent[x]
def union_parent(a, b, parent):
pa = find_parent(a)
pb = find_parent(b)
if pa == pb :
pass
elif pa < pb : # 더 큰애가 부모가 되게 설정
parent[pa] = pb
else:
parent[pb] = pa