Truy vấn kết nối DSU

Buổi 20 — Cây khung nhỏ nhất
Points
12
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho $N$ đỉnh ban đầu rời rạc nhau (đánh số từ $1$ đến $N$) và $Q$ thao tác thuộc một trong hai loại:

  • 1 u v: Nối hai đỉnh $u$ và $v$ vào cùng một thành phần liên thông.
  • 2 u v: Kiểm tra xem $u$ và $v$ có đang nằm trong cùng một thành phần liên thông hay không.
Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên t u v ($t \in {1, 2}, 1 \le u, v \le N$).
Dữ liệu ra
  • Với mỗi truy vấn loại 2, in ra YES nếu $u$ và $v$ liên thông, ngược lại in ra NO trên một dòng.
Ví dụ
Input Output
4 5
2 1 2
1 1 2
2 1 2
1 2 3
2 1 3
NO
YES
YES
3 4
2 1 1
1 1 3
2 2 3
2 3 1
YES
NO
YES
Giới hạn
  • $1 \le N, Q \le 10^5$
Draft saved