[백준/union-find] 1717번: 집합의 표현(골드5, python)

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

1717번: 집합의 표현

아이디어

union-find로 풀었다.

시간 초과가 나서 계속 찾아봤는데 input 함수를 sys.stdin.readline으로 변경해주어야 했다..

전체 코드

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

def find(x):
    if parents[x] != x:
        parents[x] = find(parents[x])
    return parents[x]

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

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


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