Truy vấn khả năng đến được
Đề bài
Mô tả
Cho một đồ thị có hướng gồm đỉnh và cạnh. Trả lời truy vấn: với mỗi truy vấn , hỏi đỉnh có thể đến được từ đỉnh không?
Dữ liệu vào
- Dòng đầu: ba số nguyên , , .
- dòng tiếp theo: mỗi dòng gồm hai số nguyên và mô tả một cạnh có hướng từ đến .
- dòng tiếp theo: mỗi dòng gồm hai số nguyên và mô tả một truy vấn.
Dữ liệu ra
Với mỗi truy vấn, in ra YES nếu có thể đến được từ , ngược lại in ra NO.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 3 1 2 2 3 3 1 4 3 1 3 1 4 4 1 |
YES NO YES |
Đồ thị có chu trình 1→2→3→1 và cạnh 4→3. Truy vấn 1→3: YES (đường đi 1→2→3). Truy vấn 1→4: NO (không có đường từ 1 đến 4). Truy vấn 4→1: YES (đường đi 4→3→1). |
| 3 2 3 1 2 2 3 1 3 3 1 2 2 |
YES NO YES |
DAG đơn giản 1→2→3. Truy vấn 1→3: YES. Truy vấn 3→1: NO (đồ thị không có chu trình). Truy vấn 2→2: YES (đỉnh có thể đến được chính nó). |
Bình luận