📖문제

학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.

1. '팀 합치기' 연산은 두 팀을 합치는 연산이다.
2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.

선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다.
  (1 <= N, M <= 100,000)
• 다음 M개의 줄에는 각각의 연산이 주어진다.
• '팀 합치기' 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다.
• '같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 속한 팀을 합친다는 의미이다.
• a와 b는 N 이하의 양의 정수이다.

출력 조건

• '같은 팀 여부 확인' 연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.

📝풀이과정

• 대표적인 서로소 집합 알고리즘 문제이다.
• N과 M의 최댓값이 100,000이기 때문에 경로 압축 방식의 서로소 집합 자료구조를 이용해야 한다.

1. '팀 합치기' 연산은 서로소 집합 알고리즘의 union연산으로, '팀 찾기' 연산은 find연산으로 구현한다.
2. '같은 팀 여부 확인'은 '팀 찾기' 연산으로 각각의 팀을 구한 후에 같은 팀이면 'YES', 다른 팀이면 'NO'를 출력하도록 한다.

⌨코드

# a번 학생의 있는 팀 찾기
def find_team(a):
  # 루트 노드가 아니면, 루트 노드를 찾을 때까지 재귀적으로 호출
  if team[a] != a:
    team[a] = find_team(team[a])
  return team[a]

# a와 b의 팀 합치기
def union_team(a, b):
  a = find_team(a)
  b = find_team(b)
  if a > b:
    team[a] = b
  else:
    team[b] = a

n, m = map(int, input().split())

team = [0] * (n + 1)
# 처음에는 서로 다른 팀으로 구분되어 총 N + 1개 팀이 존재한다.
for i in range(n + 1):
  team[i] = i

for _ in range(m):
  op, a, b = map(int, input().split())
  
  # '팀 합치기' 연산
  if op == 0:
    union_team(a, b)
  # '같은 팀 여부 확인' 연산
  elif op == 1:
    if find_team(a) == find_team(b):
      print("YES")
    else:
      print("NO")