[백준 1717] 집합의 표현 (python)

1717번: 집합의 표현

---

 

Kruskal 알고리즘을 이용하자

 

1. 모든 수가 처음에 자기 자신을 root로 가지는 root배열을 생성한다.
2. findRoot함수를 통해 입력받은 두 수의 root를 찾는다.
3. q가 0이면 두 root를 비교하여 출력한다.
4. q가 1이면 더 큰 root의 root를 작은 root로 바꾸어준다.

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int, input().split())
root = [i for i in range(N+1)]


def findRoot(x):
    if root[x] != x:
        root[x] = findRoot(root[x])
    return root[x]


for _ in range(M):
    q, a, b = map(int, input().split())
    aRoot = findRoot(a)
    bRoot = findRoot(b)
    if q:
        if aRoot == bRoot:
            print("YES")
        else:
            print("NO")
    else:
        if aRoot < bRoot:
            root[bRoot] = aRoot
        else:
            root[aRoot] = bRoot