GRAPH - Lại đồ thị

Giới hạn
  • Thời gian: 0.699s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Ngoài lề một tí

Nếu bạn là thí sinh thi VNOI OIO '09, đọc đến đây chắc hẳn bạn đang mừng lắm. Bởi vì mãi mới tìm thấy bài đồ thị “tủ” để kiếm điểm. Chắc chắn bạn sẽ càng mừng hơn nếu như tôi nói với bạn rằng bài mà bạn chuẩn bị đọc ở đây không yêu cầu thuật toán đồ thị nào cả mà chỉ hỏi về phần mà ai cũng biết đó là biểu diễn đồ thị.

Đề bài

Chú ý: đồ thị trong bài này là đồ thị có hướng.

Bạn cần viết chương trình xử lý các yêu cầu sau:

  • NEW n k, với k=0 hoặc k=1 (khởi tạo 1 đồ thị mới với n đỉnh, nếu k = 0 thì là đồ thị rỗng, nếu k = 1 thì là đồ thị đầy đủ, đồ thị đầy đủ này bao gồm n 2 cạnh, nghĩa là bao gồm cả các vòng u → u với 1 ≤ u ≤ n).
  • ADD u v (thêm cạnh từ u → v nếu chưa có).
  • DEL u v (xóa cạnh từ u → v nếu có).
  • ANY (xóa một cạnh bất kì trong đồ thị nếu có).
  • EDG u v (kiểm tra xem có cạnh từ u → v hay không).

Bạn hãy lập trình xử lý bài toán sau đây:

  • Nhập vào M yêu cầu, hãy thực hiện lần lượt từng yêu cầu.
  • Đối với những yêu cầu ANY, in ra cạnh bị xóa. Nếu không có cạnh nào thì in ra -1.
  • Đối với những yêu cầu EDG u v, in ra YES/NO tương ứng với có hay không có cạnh từ u → v.

Dữ liệu

  • Gồm nhiều dòng, mỗi dòng ghi một yêu cầu cần xử lý. Dòng cuối cùng ghi "END" báo hiệu kết thúc dữ liệu. Số yêu cầu cần xử lý không quá 10 6 .

Với yêu cầu dạng NEW, ta luôn có 1 ≤ n ≤ 1000. Dữ liệu đảm bảo yêu cầu đầu tiên luôn là yêu cầu dạng NEW và với các yêu cầu ADD, DEL, EDG, 1 ≤ u, v ≤ n.

Kết quả

Tương ứng với mỗi yêu cầu dạng ANY hay EDG là một dòng ghi kết quả.

  • Đối với yêu cầu dạng ANY, ghi ra hai số u, v cho biết bạn muốn xóa cạnh u → v.
  • Đối với yêu cầu dạng EDG, ghi ra "YES" hoặc "NO" tương ứng với việc đồ thị còn cạnh u → v hay không.

Ví dụ 

Dữ liệu
NEW 4 0
ADD 1 2
ADD 2 3
ANY
EDG 1 2
END

Với dữ liệu mẫu trên đây, hai kết quả mẫu sau đây đều hợp lệ:
Kết quả
2 3
YES

Kết quả
1 2
NO

  • Người up: paulmcvn
  • Nguồn bài: VNOI Online Informatics Olympiad '09Day 1