Editorial for Bedao Mini Contest 12 - COLORCYC


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Nếu ~m = 0~, thì số màu ít nhất cần sử dụng là ~0~.

Nếu đồ thị không có chu trình, thì số màu ít nhất cần sử dụng là ~1~.

Nếu đồ thị có chu trình, thì ta thấy cần sử dụng nhiều hơn ~1~ màu, ta có cách tô sử dụng ~2~ màu như sau: Xét cung ~(u, v)~ - Nếu ~u < v~ thì tô màu số hiệu ~1~. - Nếu ~u > v~ thì tô màu số hiệu ~2~.

Ở hai trường hợp đầu tiên, ta dễ dàng thấy nó đúng. Còn ở trường hợp thứ ba ta thấy rằng: Xét từng chu trình trong đồ thị có dạng: ~x_1, x_2, \dots, x_k, x_{k+1} = x_1~, luôn tồn tại vị trí ~h~ có ~x_{h-1} < x_h > x_{h+1}~ thì chu trình đang xét sẽ được tô hai màu. Màu ~1~ ở cung ~(x_{h-1}, x_h)~ và màu ~2~ ở cung ~(x_{h}, x_{h + 1})~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.