[백준] 1717번 - 집합의 표현 (파이썬)

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

 

# 집합의 표현
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N, m = map(int, input().split())
parent = [i for i in range(N+1)]


def union(x, y):
    a = find_parent(x)
    b = find_parent(y)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a


def find_parent(x):
    if x != parent[x]:
        parent[x] = find_parent(parent[x])
    return parent[x]


def is_set(x, y):
    if find_parent(x) == find_parent(y):
        print('YES')
    else:
        print('NO')


for _ in range(m):
    witch, a, b = map(int, input().split())
    if witch == 0:
        union(a, b)
    else:
        is_set(a, b)

 

Union-Find

입력을 받고 0이면 union함수를 1이면 is_set함수를 실행

- union함수 : 두 노드의 부모노드를 찾아내서(find_parent) 더 작은 값으로 초기화

- is_set함수 : 두 노드의 부모노드를 확인해서(find_parent) 같으면 'YES' 다르면 'NO' 출력