[백준] 1717번 - 집합의 표현

---

문제 분석

최대 원소의 개수가 1,000,000이고 질의 개수가 100,000으로 큰 편이므로 경로 압축을 하는 유니온 파인드를 통해 문제를 해결하면 된다. 따라서 다음과 같은 순서로 설계할 수 있다.

1 처음에는 노드가 연결돼 있지 않으므로 각 노드의 대표 노드는 자기 자신이다. 따라서 각 노드의 값을 자기 인덱스 값으로 초기화한다.
2 find 함수를 통해 특정 노드의 대표노드를 찾는다. 이때 0 의 경우에는 유니온을 1의 경우에는 find를 하는 과정을 거치며, union을 하는 경우에도 find함수를 이용하여 대표노드까지 가서 해당 값을 수정해준다.

❗find 함수에서 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드 값을 이번 연산에서 발견한 대표 노드로 변경하는 부분에 주의하면서 find함수를 정의한다

---

소스 코드

# 집합의 표현

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

N, M = map(int, input().split())
arr = [0 for _ in range(N + 1)]

for i in range(N + 1):
    arr[i] = i


def find(idx):  # 대표노드를 찾아 반환해주는 함수
    if idx == arr[idx]:
        return idx
    else:
        arr[idx] = find(arr[idx])
        return arr[idx]


for _ in range(M):
    menu, first, second = map(int, input().split())
    if menu == 1:
        if find(first) == find(second):
            print("YES")
        else:
            print("NO")
    elif menu == 0:
        arr[find(second)] = find(first)