Input: Cho đồ thị G=(V,E), với |V| < 10,000 đỉnh Yêu cầu: Hãy tô màu đồ thị dùng càng ít màu càng tốt
Input/Output cho bài toán: Dữ liệu vào: Từ file dothi.txt trong đó
- Dòng đầu tiên ghi hai số nguyên n và m là số đỉnh và số cạnh của đồ thị;
- Ở m dòng tiếp theo, mỗi dòng ghi 2 số nguyên tương ứng với một cạnh của đồ thị. Dữ liệu ra: File dothitomau.txt với
- dòng đầu tiên là số màu tối đa bạn dùng để tô (các màu đánh số từ 1,2,…);
- Ở n dòng tiếp theo, dòng thứ i là màu để tô đỉnh i Ví dụ Dữ liệu vào 5 5/ 1 2/ 2 3/ 3 4/ 4 1/ 1 5 Thì dữ liệu ra (với giải thích sau dấu //) sẽ là: 2 // Số màu 1 // 1 Xanh 2 // 2 Đỏ 1 // 3 Xanh 2 // 4 Đỏ 2 // 5 Đỏ
