유니온파인드 : Union Find : 서로소 집합 : 상호 배타적 집합 : Disjoint Set

https://github.com/ndb796/python-for-coding-test/blob/master/10/3.py

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

https://youtu.be/Ha0w2dJa2Nk

def find(parent, x): # 경로 압축 사용
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union(parent, a, b):
    a_p = find(parent, a)
    b_p = find(parent, b)
    if a_p < b_p:
        parent[b_p] = a_p
    else:
        parent[a_p] = b_p
        
parent = [0] * (n + 1)

for i in range(1, n+1):
	parent[i] =i

 

위의 코드가 핵심

경로 압축을 한 코드이다.

경로압축을 했는데도 시간 초과가 난다면 union by rank로 해결할 수 있다.

대부분 문제는 경로 압축으로 해결되는데 안되는 경우 union by rank를 사용하면 거의 됨