[BOJ 1717] 집합의 표현

문제 링크 : https://www.acmicpc.net/problem/1717

본문

초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 $1$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$와 $b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 $a$와 $b$가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

• $1 ≤ n ≤ 1\,000\,000$
• $1 ≤ m ≤ 100\,000$
• $0 ≤ a, b ≤ n$
• $a$, $b$는 정수
• $a$와 $b$는 같을 수도 있다.

---

풀이

딱히 설명이 필요 없는 분리 집합 기본형 문제이다. 문제에서 요구하는 쿼리을 실행하는 main() 함수를 구현하며, 각 집합을 관리하는 알고리즘으로 유니온파인드를 사용하기만 하면 된다.

소스코드

Github Link : Source Code

참고 알고리즘 : 분리 집합