Chia đồ thị
Đề bài
Mô tả
Cho một đồ thị vô hướng đơn gồm đỉnh được đánh số từ đến và cạnh.
Đồ thị được đảm bảo có một đỉnh sao cho khoảng cách từ đến mọi đỉnh khác không quá hai bước. Nói cách khác, mỗi đỉnh hoặc kề trực tiếp với , hoặc kề với một đỉnh nào đó kề với .
Nhiệm vụ của bạn là gán cho mỗi đỉnh một nhãn nhị phân ( hoặc ), tạo thành hai tập đỉnh rời nhau và , cả hai đều khác rỗng, sao cho mỗi đỉnh có nhiều nhất một đỉnh kề mang nhãn khác với nó.
Nói cách khác, tập các cạnh nối hai đỉnh khác nhãn phải tạo thành một cặp ghép (không có hai cạnh nào trong số đó chung đỉnh).
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên và : số đỉnh và số cạnh.
- Mỗi dòng trong dòng tiếp theo gồm hai số nguyên và (), cho biết có một cạnh vô hướng nối đỉnh và đỉnh .
Dữ liệu ra
- Nếu không có cách gán nhãn hợp lệ, in ra .
- Ngược lại, in ra một xâu nhị phân độ dài , trong đó ký tự thứ là nếu đỉnh thuộc và là nếu đỉnh thuộc .
Nếu có nhiều cách gán nhãn hợp lệ, in ra một cách bất kỳ.
Ràng buộc
- , , .
- Đồ thị là đồ thị đơn (không có khuyên, không có cạnh lặp).
- Tồn tại ít nhất một đỉnh có khoảng cách đến mọi đỉnh khác không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 8 1 3 1 6 2 1 2 3 2 4 3 4 4 5 5 6 |
000011 | . Các cạnh khác nhãn là và , không chung đỉnh. |
| 7 7 1 2 2 7 7 4 4 5 5 1 7 6 6 3 |
1000100 | . Các cạnh khác nhãn là và . |
| 6 8 1 2 1 6 2 6 2 3 6 4 6 5 4 5 5 3 |
-1 | Không có cách chia hợp lệ. |
Bình luận