백준 실버5 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://www.acmicpc.net/problem/1717

[나의 풀이]

⌛ 시간초과 (68% 통과)

def find(x):

    if parent[x]!=x:
        return find(parent[x])
    return x

def union(a,b):
    a = find(a)
    b = find(b)
    
    if a<b:
        parent[b]=a
    else:
        parent[a]=b


n,m = map(int,input().split())
parent = {i:i for i in range(n+1)}

check = []
for _ in range(m):
    hap, a,b = map(int,input().split())
    check.append((hap,a,b))

for case in check:
    hap, a,b = case
    if hap==0:
        union(a,b)
    else:
        if find(a)==find(b):
            print("YES")
        else:
            print("NO")

n+1까지의 숫자들이 존재하고 합집합인 두 수(a,b)를 알려주며 특정 시점마다
입력되는 두 수(x,y)가 합집합 관계인지 구하는 문제입니다.

문제를 이해하고 Union-Find라고 직감하여 바로 구현하였지만 테스트 케이스(68%)에서 재귀함수 호출 초과 에러가 발생하여 다른 풀이를 참고하였습니다.🐢🐢🐢

[다른 사람의 풀이1]

def find(x):

    if parent[x]!=x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a,b):
    a = find(a)
    b = find(b)
    
    if a<b:
        parent[b]=a
    else:
        parent[a]=b


n,m = map(int,input().split())
parent = {i:i for i in range(n+1)}

check = []
for _ in range(m):
    hap, a,b = map(int,input().split())
    check.append((hap,a,b))

for case in check:
    hap, a,b = case
    if hap==0:
        union(a,b)
    else:
        if find(a)==find(b):
            print("YES")
        else:
            print("NO")

'나의 풀이'와 같이 Union-Find를 활용한 풀이이되, Find()하는 과정에서 시간복잡도를 줄인 방식입니다.🕊️🕊️🕊️

parent[x] = find(parent[x])

의 표현으로 '나의 풀이'처럼 현재 노드의 바로 상위 부모로 초기화하는 것이 아닌 각 노드별로 최상위 부모노드를 가리키는 방식으로 초기화하여 시간복잡도를 줄인 것이 포인트였습니다.

[다른 사람의 풀이2]

import sys
input = sys.stdin.readline

# disjoint set & union-find
n, m = map(int,input().split()) 
parent = [i for i in range(n+1)]
def find(c):
  if(parent[c] == c): return c
  parent[c] = find(parent[c])
  return parent[c]

def union(ca,cb):
  rootOfca = find(ca)
  rootOfCb = find(cb)
  if not rootOfca == rootOfCb:
    parent[rootOfCb] = rootOfca

def check(ca,cb):
  if find(ca) == find(cb):
    return True
  else:
    return False

# finding answer
ans = []
for i in range(m):
  flag, a, b = map(int,input().split())
  if flag == 0 :
    union(a,b)
  else:
    if check(a,b):
      ans.append("YES")
    else:
      ans.append("NO")

for i in range(len(ans)):
  print(ans[i])

'다른 사람의 풀이1'과 같이 각 노드별 최상위 부모로 초기화한 풀이이며 두 수(ca,cb)가 같은 집합인지 확인하기 위해 check()함수화 해준 모습입니다.🐇🐇🐇

감사합니다.