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

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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ò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.

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.

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.