백준 1717 집합의 표현 python

청천·2022년 12월 1일
0

대표적인 유니온 파인드 문제
find를 할때 시간 복잡도를 위해 O(logn)으로 구현 해야한다.
이를 위한 경로 압축과 union by rank 라는 두가지 테크닉이 있다.
단 여기서 파이썬의 경우에는 재귀가 느림으로
경로 압축의 경우 재귀 깊이가 깊어지는 문제로 인해 낭패를 볼수 도 있다.

# 경로 압축
def find(x):
    if par[x] == x:
        return x
    else:
        # 리턴 받은 걸로 부모 바꾸기
        # 재귀 깊이 조심
        # 파이썬은 재귀가 느리니..
        par[x] = find(par[x])
        return par[x]

# union by rank
# 더 낮은 걸 붙인다.
def union(a, b):
    a = find(a)
    b = find(b)
    # 하나가 나머지 하나의 아래로 내려가야 한다.
    if rnk[a] > rnk[b]:
        par[b] = a
    elif rnk[a] < rnk[b]:
        par[a] = b
    else:
        par[b] = a
        rnk[a] += 1

n, m = map(int, input().split())
par = [i for i in range(n+1)]
rnk = [1 for _ in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split())

    if a == 0:
        union(b, c)
    else:
        if find(b) == find(c):
            print('YES')
        else:
            print('NO')

0개의 댓글