여행가자

출처 : 백준 #1717

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

---

문제

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

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

---

입력

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

---

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

---

입출력 예시

예제 입력 1

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1

NO
NO
YES

---

풀이

생각

• 같은 집합에 속한 원소인지 묻는 문제이다.
• 따라서 원소들의 연결을 표현하는 graph를 만들고, 각 원소들의 최상단 부모노드(가장 숫자가 작은 노드)가 같은지 여부를 확인하면 된다.

풀이 설명

• 각 원소를 연결하여 주는 union_parent과 각 원소가 같은 집합 안에 속해있는지를 알려주는 find_parent 함수를 이용하였다.
• find_parent 함수가 재귀를 이용했기 때문에 recursionlimit에 걸려 다시 세팅해주었다.
• cal이 0이면 union_parent 함수를, cal이 1이면 find_parent 함수를 사용하였다.

python code

# 백준 1717번 집합의 표현
import sys
sys.setrecursionlimit(10**6)
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

input = sys.stdin.readline
n, m = map(int, input().split())

parent = [0] * (n+1)
for i in range(1, n+1):
    parent[i] = i

answer = []
for j in range(m):
    cal, a, b = map(int, input().split())
    if cal == 0:
        union_parent(parent, a, b)
    else:
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        if a == b:
            answer.append("YES")
        else:
            answer.append("NO")


for x in answer:
    print(x)