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

백준 파이썬 1717번 집합의 표현

Gold 5

 

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

 

집합에 대한 문제다. 유니온 파인드를 활용해 풀어주면 된다.

5 5

0 1 2

0 2 3

0 4 5

0 1 5
1 1 4

막히면 위의 예시의 결과가 YES 가 나오는지 확인해보면 된다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
def find_parent(x):
    if r[x] != x:
        r[x] = find_parent(r[x])
    return r[x]
def dfs(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        r[y] = x
    else:
        r[x] = y
        
n, m = map(int, input().split())
r = [i for i in range(n+1)]
for _ in range(m):
    o, a, b = map(int, input().split())
    if o == 0:
        dfs(a,b)
    else:
        if find_parent(a) == find_parent(b):
            print("YES")
        else:
            print("NO")