boj 1717 집합의 표현(골드4)

문제

boj 1717 집합의 표현

union find 문제이다

풀이

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

n, m = map(int,input().split())
f = [i for i in range(n+1)]

def union(f,a,b):
  a = find(f,a)
  b = find(f,b)

  if a == b : return

  elif a < b:
    f[b] = a

  else :
    f[a] = b

def find(f,x):
  if f[x] == x:
    return x

  f[x] = find(f,f[x])
  return f[x]

for _ in range(m):
  q,a,b = map(int,input().split())
  if q == 0:
    union(f,a,b)
  else:
    print("YES" if find(f,a) == find(f,b) else "NO")

생각할점

처음에 yes를 출력하기위해 비교하는 부분에서
if find(f,a) == find(f,b) 가 아니라
f[a] == f[b] 로 비교해서 틀렸다

union find 문제 풀때는 꼭 find 한걸로 비교해야되나보다

그냥 f로 비교해도 다 최소숫자로 갱신되어있다고 생각했는데
union 함수 구성할때도 a = f[a] 가 아니라 a=find(f,a)로 비교해야만 하는걸 보니 그렇게 안하면 안되는 경우가 있는것같다

사실 그 반례를 아직 못찾았는데 일단 find한걸로 비교하기 받아들이고 천천히 생각해봐야겠다