백준 1717

<집합의 표현>

난이도 : 골드 5

1. 백준 문제

1717

2. 코드 알고리즘

3. 코드

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

import sys

input = sys.stdin.readline

n,m = map(int, input().split())

parent = [0]*(n+1)

#find 연산
def find(a):
    if parent[a] == a:
        #부모 노드가 자기자신이면 자기자신 return
        return a
    else:
        #부모 노드의 부모노드 찾기
        '''놓친 부분'''
        parent[a] = find(parent[a]) #★경로 압축, 가르키는 부모노드를 다 루트노드로 바꾸기★
        return parent[a] #else에서도 return문 시행, if문에서 시행한 return은 else의 find문에서 소요
        #한번 더 return문 시행해야 함수가 완전히 종결

#union 연산
def union(a, b):
    #a와 b의 대표 노드 찾기
    parent_a = find(a) #find(3)
    parent_b = find(b)
    #두 원소의 대표 노드끼리 연결
    #b의 대표노드를 a의 대표노드에 맞추기
    parent[parent_b] = parent_a #b가 가리키는 부모노드를 변경할 필요는 없음

def checksame(a,b):
    parent_a = find(a)
    parent_b = find(b)
    if parent_a == parent_b:
        return True
    else:
        return False

for i in range(1, n+1):
    #초기 세팅, 자신이 가르키는 부모노드를 일단 자기 자신으로 설정
    parent[i] = i

for i in range(m):
    piv, a, b = map(int, input().split())
    if piv == 0:
        union(a,b)
    else:
        if checksame(a,b):
            print("YES")
        else:
            print("NO")

4. 후기

find 함수를 정의할 때 경로압축 + return문 생략
재귀함수를 설정하다보니 헷갈렸나 보다
else문에서 실행된 find(a)의 return문이 if문에서 실행된 return문!
함수가 완전히 종료되기 위해서는 마지막 줄에
return parent[a] 입력

++ 경로 압축을 위해 재귀함수에서 다시 원형으로 돌아오는 과정에 가르키는 부모노드 루트노드로 설정하기
parent[a] = find(parent[a])