백준 1717. 집합의 표현

https://www.acmicpc.net/problem/1717

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def _union(A, B): # 최대 높이를 확인해서 효율적으로 합쳐주기!
    A = _find(A)
    B = _find(B)

    if A == B:
        return

    # rank가 높은 친구한테 낮은 친구를 붙여주는게 더 이득!
    if rank[A] < rank[B]:
        par[A] = B
    elif rank[B] < rank[A]:
        par[B] = A
    else:
        par[A] = B
        rank[B] += 1

def _find(A):
    if par[A] == A: # 스스로를 부모로 칭하고 있다면?
        return A
    else:
        par[A] = _find(par[A]) # 경로 압축(고속도로 뚫기)
        return _find(par[A])

N, M = map(int,input().split())
rank = [0] * (N + 1)
par = [i for i in range(N+1)]

for _ in range(M):
    X,A,B = map(int,input().split())

    if X == 0:
        _union(A,B)
    else:
        if _find(A) == _find(B):
            print("YES")
        else:
            print("NO")

 

Union-Find 알고리즘에서 랭크(rank)가 높은 쪽으로 낮은 쪽을 붙이는 이유

: 트리의 깊이가 늘어나지 않게 되어 효율적이기 때문! 

예시

1. 트리의 높이가 3인 집합과 높이가 1인 집합을 합칠 때, 높이 1인 트리를 높이 3인 트리에 붙이면 트리의 높이가 여전히 3으로 유지됩니다.
2. 만약 반대로 높이 3의 트리를 높이 1의 트리에 붙인다면, 결과적으로 트리의 높이는 4가 되며 이후 _find 연산에서 더 많은 단계가 필요하게 됩니다.

+ 높이가 같은 두 트리를 합치면 한칸 내려가서 붙으므로 +1