Hướng dẫn giải của Ghép Cặp Tương Thích
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Lời giải: Ghép Cặp Tương Thích
Hướng tiếp cận
Xây dựng đồ thị: mỗi đỉnh là một ID, cạnh nối hai ID có tổng bằng hoặc . Mỗi đỉnh có tối đa 2 cạnh kề. Đồ thị gồm các đường đi và chu trình.
Thuật toán
- Xây dựng danh sách kề.
- Lặp: tìm đỉnh bậc 1, ghép tối đa cặp trên cạnh đó, xóa cạnh.
- Khi xóa cạnh, kiểm tra đỉnh kề — nếu bậc giảm về 1 hoặc hết bò, tiếp tục xử lý.
Độ phức tạp
- Thời gian:
Bình luận