(python) 1717 집합의표현 - 유니온 파인드

기본적인 유니온 파인드 문제.

 

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)

추가적으로 다른 사람의 코드를 보니 유니온 과정을 하기 전에 자신이 가지고 있는 집합의 개수가 적은 쪽을 큰 쪽으로 옮기는 동작으로 코드를 짜서 좋은 성능을 낸 경우가 있었다.

 

이 방법을 이용하면 유니온 파인드 코드 성능을 늘릴 수 있을 것이다.