[Python] 백준 / gold / 1717 : 집합의 표현

문제 링크 : https://www.acmicpc.net/problem/1717

분리 집합, 서로소 집합 문제다. 집합의 루트 노드를 설정하고, 그 노드를 집합의 이름처럼 사용해서 풀 수 있다. 보통은 집합 안에서 값이 가장 작은 원소를 루트 노드로 두는 것이 관례적이다. 오랜만에 이런 유형을 풀어봐서 리마인드 하기 좋은 문제였던거 같다.

3가지 기억할 것

1. 최소 힙, 최대 힙도 엄밀히는 트리 자료구조에 속한다.
2. 트리로 서로소 집합 자료구조를 구현할 수 있다.
3. 서로소 집합 문제는 루트 노드 테이블을 갱신하면서 풀 수 있다.

파이썬 코드

import sys
sys.setrecursionlimit(10**6)
N, M = map(int, sys.stdin.readline().split())
parent = [x for x in range(N+1)]
answer = []


def findParent(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = findParent(parent[x])
        return parent[x]


for _ in range(M):
    x, a, b = map(int, sys.stdin.readline().split())
    if x == 0:
        pa = findParent(a)
        pb = findParent(b)
        parent[max(pa, pb)] = min(pa, pb)

    elif x == 1:
        if findParent(a) == findParent(b):
            answer.append("YES")
        else:
            answer.append("NO")

for a in answer:
    print(a)