문제

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

풀이

문제 설명
첫째 줄에 n과m이 주어지고
{0}부터 {n}까지 총 n+1개의 집합이있고
둘째 줄부터 m개의 연산이 주어지는데 연산은 두가지 형식으로 주어진다.

1.1 a b형식이면 두원소가 같은집합인지 확인후 맞다면 YES출력 아니라면NO출력
2.0 a b형식이면 합집합 연산

단순히 union-find자료구조를 조건에 맞게 구현해주면 된다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def find_parent(parent, x):
  if x != parent[x]:
    parent[x] = find_parent(parent, parent[x])
    return parent[x]
  return 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
    
n, m = map(int, input().split())
parent = [0] * (n+1)

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

for _ in range(m):
  oper, a, b = map(int, input().split())
  
  if(oper == 0):
   union_parent(parent, a, b)
  elif(oper == 1):
    if(find_parent(parent, a) == find_parent(parent, b)):
      print('YES')
    else:
      print('NO')