Hướng giải của Đồ Thị Hai Phía Động
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Lời Giải: Đồ Thị Hai Phía Động
Ý tưởng: Parity DSU Rollback
Mở rộng DSU Rollback với parity (0 = cùng phía, 1 = khác phía với root):
dist[v]= khoảng cách parity từ \(v\) đến root của nó.- Khi thêm cạnh \((u,v)\): tính
du, dv(parity từ \(u,v\) đến root của chúng).- Nếu cùng root: chu trình. Nếu
du XOR dv == 0→ chu trình lẻ → không bipartite. Tăngodd_count. - Nếu khác root: gộp bình thường, điều chỉnh parity root.
- Nếu cùng root: chu trình. Nếu
- Đồ thị bipartite khi
odd_count == 0.
Offline Segment Tree + D&C: tương tự dsur-online, nhưng tại mỗi lá query → in odd_count == 0 ? "YES" : "NO".
Lưu ý quan trọng
- Khi gộp hai tập đã nối nhau (cùng root), vẫn phải push vào stack để đảm bảo rollback đúng.
odd_countcũng phải được rollback khi undo thao tác gây ra chu trình lẻ.
Độ phức tạp
\(O(Q \log^2 N)\).
Nhận xét