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

💡문제접근

• 분리 집합 알고리즘에 대한 부분은 한 번도 공부한 적이 없어서 Youtube를 통해서 영상을 시청한 다음 분리 집합에 대한 개념이 정립된 다음 코드를 작성했다. 자세한 부분은 [알고리즘] 시리즈에 기록할 예정이다.
• 분리 집합 알고리즘이란? : [분리 집합]

💡코드(메모리 : 77536KB, 시간 : 320ms)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = map(int, input().strip().split())
parent = [i for i in range(n+1)]

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for _ in range(m):
    op, a, b = map(int, input().strip().split())
    if not op:
        union_parent(parent, a, b)
    else:
        if find_parent(parent, a) == find_parent(parent, b):
            print("YES")
        else:
            print("NO")

💡소요시간 : 1h