백준) 1717번_집합의 표현 (python)

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

1717번: 집합의 표현

나의 풀이

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

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

def find(a):
    if a == arr[a]:
        return a
    arr[a] = find(arr[a])
    return arr[a]

def union(a,b):
    pa = find(a)
    pb = find(b)
    arr[pa] = pb


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

• Union - find 알고리즘 사용
• 1 <= n <=1,000,000
• 1<=m<=100,000
• 수가 커서 sys.setrecursionlimit(100000)으로 제한해준다!