[백준/파이썬] 1717번

📍백준 1717 문제

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

코드

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

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

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


def findArr(x):
    if arr[x] != x:
        arr[x] = findArr(arr[x])
    return arr[x]


def unionArr(a, b):
    a = findArr(a)
    b = findArr(b)
    if a < b:
        arr[b] = a
    else:
        arr[a] = b


for _ in range(m):
    cmd, a, b = map(int, input().split())
    if cmd == 0:
        unionArr(a, b)
    else:
        if findArr(a) == findArr(b):
            print("YES")
        else:
            print("NO")

풀이

집합을 결합할 때, 작은 값을 부모로 설정하여 값을 결합해주면 된다.
{1}과 {3}을 결합하고 싶다면 배열 내 인덱스가 3인 자리에 1의 값을 넣어주면 된다. => [0,1,2,1,4,5]
그래서 같은 집합 안에 값이 있는지 확인하려면, 부모가 같은지 확인해주면 된다.