난이도 : 골드 5
유형 : 유니온 파인드
https://www.acmicpc.net/problem/1717

---

문제

맨 앞에 숫자가 0이냐 1이냐에 따라

0 a b → a와 b가 포함된 집합을 합침 (Union)

1 a b → a와 b가 같은 집합에 속해있는지 확인 (Find)

1 연산의 결과 YES or NO 를 출력해주는 문제이다.

유니온 파인드(Disjoint Set Union, DSU)란?

유니온 파인드는 서로소 집합(Disjoint Set)을 표현하고,
두 원소가 같은 집합에 속해 있는지를 빠르게 판별할 수 있게 해주는 자료구조이다.

• 서로소인 여러 개의 집합을 관리할 때 사용함.
• 대표적으로 네트워크 연결 여부 확인, 싸이클 판별, 최소 신장 트리(Kruskal) 등에 사용됨.

유니온(Union)
"A와 B를 같은 그룹으로 묶어줘!"

예: union(1, 3) → 1번과 3번이 같은 집합(팀)이 됨

파인드(Find)
"얘는 어떤 그룹(대표자)에 속해 있어?"

예: find(3) → 3번은 1번과 같은 집합이니까 1 (대표)을 반환

---

해답 및 풀이

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

# 대표 노드(부모) 배열 초기화
n, m = map(int,input().split())
parent = [i for i in range(n+1)]

# find 연산 : x의 부모(루트) 를 찾아준다.
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

# union 연산: a, b 의 대표를 찾아서 같은 집합으로 합친다.
def union(a, b):
    a_root = find(a)
    b_root = find(b)
    if a_root != b_root:
    	parent[b_root] = a_root # 한 쪽을 다른 쪽에 붙임


# 명령어 처리
for _ in range(m):
    cmd, a, b = map(int,input().split())
    if cmd == 0:
        union(a, b)
    elif cmd == 1:
        print("YES" if find(a) == find(b) else "NO")

이게 어떤 흐름으로 진행되냐면,
만약 초기 n = 5 라면,
parent = [0, 1, 2, 3, 4, 5] 가된다.
즉 parent[1] = 1, parent[2] = 2, ... 모두 자기 자신이 루트이다.

union(1,2)를 한다면
find(1) -> 1, find(2) -> 2 가 되고
1 != 2 이므로
parent[2] = 1 로 2번이 1번을 부모로 갖게 된다.

이때 parent 배열은 [0,1,1,3,4,5] 가 된다.

다음으로 union(3,4) 를 한다면, 같은 방식으로
parent =[0,1,1,3,3,5] 가 된다.

그리고 union(2,3) 연산을 한다면
parent[2]와 parent[3] 은 각각 1과 3이므로
parent[3] 또한 1을 부모로 가진다.

parent = [0,1,1,1,3,5]

만약 이 상태에서 find(4) 를 한다면?
find(4)
-> parent[4] = 3, 그런데 4 != 3 이므로
parent[4] = find(parent[4]) 가 되므로
find(3) 이 되어 1이 된다.

즉 parent[4] = 1 로 경로 압축이 된다.

최종 parent = [0, 1, 1, 1, 1, 5] 로
1,2,3,4 는 모두 같은 집합에 속해있고 5는 아직 혼자있다는 의미이다.