악곱 == 악성곱슬

유니온 파인드

---

해당 문제는 유니온 파인드(서로소 집합)의 대표적인 유형이다. find연산과 union연산은 아래와 같이 구현하여 풀 수 있다. 초기 시작은 여러 방법이 있는데 -1로 초기화 하는 방법도 있고 자기 자신을 부모로 놓고 푸는 방법이 있다.

아래 코드는 자기 자신을 부모로 구현한 방식이다. 재귀함수를 구현할 때, 재귀가 깊어질 수 있기 때문에 sys 모듈의 setrecursionlimit을 이용하자.

import sys

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

def solution(n, m):
    parent = [0] * (n + 1)
    for i in range(n + 1):
        parent[i] = i
    for _ in range(m):
        cmd, a, b = map(int, sys.stdin.readline().rstrip().split())
        if cmd == 0:
            union_parent(parent, a, b)
        else:
            if find_parent(parent, a) == find_parent(parent, b):
                print("yes")
            else:
                print("no")

if __name__ == "__main__":
    sys.setrecursionlimit(100000)
    N, M = map(int, sys.stdin.readline().rstrip().split())
    solution(N, M)