Disjoint Set Union: Truy Vấn Liên Thông Động
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Ban đầu có N phần tử rời nhau từ 1 đến N. Có Q truy vấn thuộc hai loại:
1 u v: Hợp nhất hai tập hợp chứauvàv.2 u v: Kiểm tra xemuvàvcó đang thuộc cùng một tập hợp hay không.
Dữ liệu vào (Input)
- Dòng 1: Hai số nguyên dương
NvàQ(1 ≤ N, Q ≤ 2 × 10^5). Qdòng tiếp theo: Mỗi dòng gồm 3 số nguyêntype u v.
Dữ liệu ra (Output)
- Với mỗi truy vấn loại
2, in raYESnếuuvàvcùng tập hợp, ngược lại inNO.
Ví dụ mẫu
Sample Input 1
5 5
1 1 2
1 2 3
2 1 3
2 1 4
1 3 4
Sample Output 1
YES
NO
Community Discussion