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

문제

풀이

union-find 알고리즘을 사용했다.

union find란?

https://velog.io/@sunz8281/union-find

두 노드가 같은 유니온에 있는지 찾는 알고리즘

설명

union 연산 : a의 루트 노드를 b의 루트 노드로 연결해 같은 유니온으로 합치는 연산
find 연산 : root 노드 조회

0이 입력되었을 때, union 연산을 수행한다.

1이 입력되었을 때, 즉 두 원소가 같은 집합에 포함되어 있는지 확인할 때는 두 노드에 find 연산을 하여 같은지 비교한다.

코드

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
parent = [i for i in range(n+1)]

def root(x): # 루트 노드 구하는 함수
    if parent[x] == x:
        return x
    parent[x] = root(parent[x]) # 루트 노드를 빠르게 찾기 위해 경로 축소
    return parent[x]

for i in range(m):
    x, a, b = map(int, input().split())
    if x==0:
        parent[root(a)] = root(b) # union 연산
    else:
        print("YES" if root(a) == root(b) else "NO")

sys.setrecursionlimit(10**6)를 넣지 않으면 런타임 에러가 뜬다,,,, 유의하도록 하자.