cpp-171Đọc toàn bộ đề miễn phí
DSU Có Hoàn Tác - Tính Liên Thông Động Ngoại Tuyến (Dynamic Connectivity)
Ban đầu có một đồ thị rỗng gồm N đỉnh (đánh số từ 1 đến N) và không có cạnh nào.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: Disjoint Set Union by Rank, Segment Tree over Time.
Nội dung đề bài
Mô tả bài toán
Ban đầu có một đồ thị rỗng gồm N đỉnh (đánh số từ 1 đến N) và không có cạnh nào.
Có Q sự kiện xảy ra theo thứ tự thời gian:
+ u v: Thêm một cạnh vô hướng giữa đỉnh u và v.- u v: Xóa cạnh vô hướng giữa đỉnh u và v (đảm bảo cạnh này đang tồn tại).? u v: Truy vấn xem hai đỉnh u và v có thuộc cùng một thành phần liên thông tại thời điểm hiện tại hay không.
Hãy trả lời YES hoặc NO cho tất cả các truy vấn dạng ?.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng đầu chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 105).
- Q dòng tiếp theo, mỗi dòng mô tả một sự kiện thuộc 3 loại trên (1 ≤ u, v ≤ N, u ≠ v).
Output
- Với mỗi sự kiện dạng
?, in raYEShoặcNOtrên một dòng.
Ràng buộc
- Thời gian chạy tối đa: 1500ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
3 5
+ 1 2
? 1 2
? 1 3
- 1 2
? 1 2Output
YES
NO
NOGiải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.