import sys
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
li = [i for i in range(N+1)]
def union(x, y):
rootx = find(x)
rooty = find(y)
if rootx != rooty:
li[rooty] = rootx
def find(x):
if li[x] == x:
return x
else:
parents = find(li[x])
li[x] = parents #이 과정을 빼먹으면 안된다. 성능개선에 중요한 부분, 다음 부모노드 접근이 빨라진다.
return parents
for _ in range(M):
oper, x, y = map(int, input().rstrip().split())
if oper == 1:
if find(x) == find(y):
print('yes')
else: print('no')
else :
union(x,y)
추가적으로 다른 사람의 코드를 보니 유니온 과정을 하기 전에 자신이 가지고 있는 집합의 개수가 적은 쪽을 큰 쪽으로 옮기는 동작으로 코드를 짜서 좋은 성능을 낸 경우가 있었다.
이 방법을 이용하면 유니온 파인드 코드 성능을 늘릴 수 있을 것이다.
'Python' 카테고리의 다른 글
정규식 연산 이용하기 (0) | 2020.07.13 |
---|---|
python 내장함수 zip 다루기 (0) | 2020.07.10 |
(python) 백준 균형잡힌 세상 - re 정규 연산 풀이 (0) | 2020.06.24 |
(python) 14889 스타트와 링크 (0) | 2020.06.23 |
(python) 백준 14888 연산자 끼워 넣기 (0) | 2020.06.22 |