trang chủ / đề bài / reachqry

Truy vấn khả năng đến được

Đề bài

Mô tả

Cho một đồ thị có hướng gồm n đỉnh và m cạnh. Trả lời q truy vấn: với mỗi truy vấn (a,b), hỏi đỉnh b có thể đến được từ đỉnh a không?

Dữ liệu vào

  • Dòng đầu: ba số nguyên n, m, q.
  • m dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b mô tả một cạnh có hướng từ a đến b.
  • q dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra YES nếu b có thể đến được từ a, ngược lại in ra NO.

Ràng buộc

  • 1≤n≤5·104
  • 1≤m,q≤105

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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0