1717: 집합의 표현

풀이 시간

• 7m

구현 방식

• 분리 집합 == 서로소 집합

• find: 부모를 찾는 함수

• union: 부모를 합쳐주는 함수

코드

import sys

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

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

N, M = map(int, sys.stdin.readline()[:-1].split())
parent = [i for i in range(N+1)]
for m in range(M):
    cmd, a, b = map(int, sys.stdin.readline()[:-1].split())
    if cmd == 0:
        union(parent, a, b)
    elif cmd == 1:
        if find(parent, a) == find(parent, b):
            print("YES")
        else:
            print("NO")

결과