[코드조각] union-find (분리집합)

python에서 분리집합을 하기 위한 find 함수와 union함수. 둘 다 최악의 경우 시간복잡도 O(n)을 기록한다

# P[i]는 i가 속한 집합의 대표값이 담겨있다.

def find(n):
    
    if P[n] == n:
        return n
    
    P[n] = find(P[n])
    
    return P[n]

def union(u, v):

    u = find(u)
    v = find(v)

    if u == v:
        return

    if u != v:
        P[v] = u