대표적인 유니온 파인드 문제
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')