Hướng dẫn giải của Kiểm Tra Bò
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: Kiểm Tra Bò
Hướng tiếp cận
Sử dụng Union-Find để theo dõi các thành phần liên thông và xóa từng đỉnh theo thứ tự ngược lại.
Nhận xét quan trọng
- Xử lý từ đỉnh cuối cùng về đầu tiên dễ hơn việc xóa từng đỉnh.
- Khi thêm đỉnh lại, nếu bit tương ứng là 1, chúng ta nối tất cả hàng xóm lại.
Thuật toán
- Đảo ngược thứ tự xóa - xử lý từ cuối về đầu.
- Sử dụng Union-Find để theo dõi các thành phần.
- Với mỗi bước, nếu cần, nối các hàng xóm lại và ghi lại kết quả.
Độ phức tạp
- Thời gian:
- Bộ nhớ:
Bình luận