Đề bài cho 2 loại truy vấn
1 u v : Cho 2 món u, v thuộc 2 loại khác nhau
2 u v : Kiểm tra 2 món u, v trả về :
DUNNO -> Chưa đủ dữ kiện trả lời
SAFE -> Chung nhóm gia vị
FATAL -> Khác nhóm gia vị
Để giải bài toán này thì trước tiên ta cần phải chia kết quả n hũ gia vị thành 2 phần 1 phần sẽ có
giá trị là 0 và hiển nhiên phần còn lại giá trị 1.
Thì ta nhận thấy rằng nó khá giống với đồ thị 2 phía à ừ vậy thì ở đây ta có ý tưởng như sau:
Với cấu trúc Dsu ta sẽ thêm mảng color với color[u] là độ chênh lệch của đỉnh u so với đỉnh gốc
của u hay tương đương đỉnh gốc của u là đỉnh mà ta sẽ thêm vào món ăn nên đỉnh các đỉnh còn lại
sẽ tùy thuộc vào đỉnh gốc này. Vì là đỉnh gốc nên color[root] = 0 như việc ban đầu gốc chỉ có 1
đỉnh là chính nó nên màu của nó phụ thuộc vào chính nó nên sẽ giống màu với đỉnh gốc còn.
các đỉnh còn lại nếu cùng nhóm với root và cùng loại với root sẽ mang color[u] = 0 và ngược lại
không cùng nhóm nên độ chênh lệch với root color[u] = 1.
Dựa vào định nghĩa color trên ở đây ta cần xây dựng một Dsu trả lời các truy vấn 2 như sau :
1 - Chưa đủ dữ kiện trả lời : 2 đỉnh này chưa có ràng buộc gì tới nhau => khác thành phần liên thông
2 - Chung nhóm gia vị : 2 đỉnh này phải chung thành phần liên thông và độ chênh lệch của nó với nút
gốc là bằng nhau (color cả 2 khác color root hoặc color cả 2 bằng color root)
=> color[u] ^ color[v] = 0
3 - Khác nhóm gia vị : tương tự như chung nhóm gia vị nhưng mà 2 đỉnh này phải chênh lệch nhau về màu
nghĩa là color[u] ^ color[v] = 1
Code mẫu tham khảo : https://ideone.com/TdWZHs
The_Blacksiler
Created at
2 likes