문제
접근
유니온-파인드의 아마 가장 기본 연습 문제가 아닐까 생각된다.
이미 이전에 한번 풀었기 때문에 크게 문제는 없었다.
풀이 자체가 이전 문제와 비슷하기 때문에 사이클 게임을 참고.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys
input = sys.stdin.readline
n, m = map(int, input().split(' '))
parent = [-1 for i in range(n+1)]
def union(x, y):
x = find_parent(x)
y = find_parent(y)
if x == y:
return
if parent[x] < parent[y]:
parent[x] += parent[y]
parent[y] = x
else:
parent[y] += parent[x]
parent[x] = y
def find_parent(x):
if parent[x] < 0:
return x
else:
y = find_parent(parent[x])
parent[x] = y
return y
for _ in range(m):
command, a, b = map(int, input().split(' '))
if command == 0:
union(a,b)
else:
a = find_parent(a)
b = find_parent(b)
if a==b:
print('YES')
else:
print('NO')