Mạng Lưới Gián Điệp

Buổi 43 — SCC (Tarjan) & 2-SAT
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Có N gián điệp và M kênh liên lạc một chiều. Mỗi kênh cho phép gián điệp u gửi tin cho gián điệp v.

Một nhóm gián điệp là một tập hợp cực đại các gián điệp mà bất kỳ hai người nào trong nhóm đều có thể liên lạc với nhau (trực tiếp hoặc gián tiếp thông qua các thành viên khác trong nhóm).

Cho Q truy vấn, mỗi truy vấn gồm hai số a b. Với mỗi truy vấn, trả lời xem a có thể gửi tin đến b (trực tiếp hoặc gián tiếp) hay không.

Dữ liệu vào
  • Dòng đầu: ba số nguyên N, M, Q (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ Q ≤ 200000)
  • M dòng tiếp theo: u v
  • Q dòng tiếp theo: a b
Dữ liệu ra
  • Q dòng, mỗi dòng "YES" hoặc "NO".
Ví dụ
Input Output
4 4 3\n1 2\n2 3\n3 1\n3 4\n1 3\n1 4\n4 1 YES\nYES\nNO
Giới hạn
  • 1 ≤ N ≤ 100000
  • 0 ≤ M ≤ 200000
  • 1 ≤ Q ≤ 200000
Draft saved