Mình xin chia sẻ lời giải bài này như sau:

Gọi \(Edges[i]\) là vector chứa tất cả các đỉnh kề với đỉnh \(i\).

Khi đó ta có : Số màu tối thiểu cần dùng để thoả mãn yêu cầu bài toán chính với \(Max(Edges[i].size())\) với \(i=1,2,...,n\).

Và ta sẽ đi chứng minh điều này như sau:

• Đặt \(f = Max(Edges[i].size()) \forall i=1,2,...,n\)

Khi đó việc chứng minh sẽ gồm \(2\) phần sau:

• Ta sẽ chứng minh những giá trị nhỏ hơn \(f\) sẽ không thoả mãn yêu cầu bài toán \(\implies\) Điều này rõ ràng vì nếu ta dùng \(t\) màu để tô với \(t\) nhỏ hơn \(f\) thì khi đó tồn tại đỉnh \(j\) với \(f=Edges[j].size()\) sẽ không thoả mãn yêu cầu bài toán.

• Ta sẽ chứng minh, với \(f\) màu, ta sẽ tồn tại một cách tô thoả mãn yêu cầu bài toán, cụ thể ta tô như sau:

Gọi bốn màu ta cần tô là màu \(1,2,3,4\).

Khi đó ta tô như sau:

• Xét một đỉnh \(i\) bất kì, và gọi \(j\) là một đỉnh bất kỳ thuộc tập \(edges[i]\) và đã được tô màu \(k\).

Khi đó ta sẽ tô màu tất cả các đỉnh còn lại trong \(edges[i]\) theo quy luật sau: \((k+1)\text{ mod }f+1,(k+2)\text{ mod }f+1,...\) cho đến hết các đỉnh \(edges[i]\). Vì số lượng màu tối đa ta có thể dùng trong một tập \(edges[i]\) là \(f\), nên rõ ràng với cách tô như vậy, những đỉnh được tô mà kề với \(i\) sẽ khác nhau từng đôi một. (Để hiểu rõ hơn, các bạn có thể xem mình minh hoạ).

Như vậy là ý tưởng tô màu đã hoàn thiện.

Việc còn lại chỉ là code.

Thì ở đây, mình sử dụng bfs để tô màu các đỉnh kết hợp với mảng points_edges[]. Mảng này có tác dụng lưu lại màu \(k\) của đỉnh \(j\) đã được tô trong tập đỉnh \(edges[i]\)

Cụ thể các bạn có thể xem code tại đây

Như vậy là bài toán đã được giải quyết, nếu có gì không hiểu các bạn comment nhé !