Disjoint Set Union: Truy Vấn Liên Thông Động

Buổi 25 — Disjoint Set Union Data-structures Graphs
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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ứa u và v.
  • 2 u v: Kiểm tra xem u và v có đ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 N và Q (1 ≤ N, Q ≤ 2 × 10^5).
  • Q dòng tiếp theo: Mỗi dòng gồm 3 số nguyên type u v.
Dữ liệu ra (Output)
  • Với mỗi truy vấn loại 2, in ra YES nếu u và v cùng tập hợp, ngược lại in NO.
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
Draft saved