solution

Cấp phát thanh ghi (register allocation) thường được mô hình hoá bằng bài toán tô màu đồ thị giao nhau (interference graph): mỗi biến tạm là một đỉnh; hai đỉnh có cạnh nối nếu hai biến đó "sống" cùng lúc tại một điểm nào đó trong chương trình, nên không được cấp cùng một thanh ghi. Bài này cho trực tiếp đồ thị giao nhau (không cần tính sống) và yêu cầu tô màu bằng thuật toán tham lam với thứ tự xử lý đỉnh xác định sau (để kết quả là duy nhất):

1. Xét các đỉnh theo thứ tự bậc giảm dần; nếu hai đỉnh cùng bậc, đỉnh nào xuất hiện trước trong danh sách đỉnh của input được xét trước.
2. Khi đến lượt một đỉnh, gán cho nó thanh ghi (đánh số từ $0$) là số nhỏ nhất chưa được dùng bởi bất kỳ đỉnh kề nào đã được tô màu tính đến thời điểm đó (chỉ quan tâm đỉnh kề đã tô hay chưa, không quan tâm nó được xử lý trước hay sau đỉnh hiện tại theo thứ tự gốc trong input).

Cho $k$ là số thanh ghi vật lý sẵn có (đánh số $0,\dots,k-1$). Sau khi tô màu toàn bộ đồ thị theo thuật toán trên (quá trình tô luôn thành công, không giới hạn số màu khi đang tô):

• Nếu tổng số màu khác nhau đã dùng $\le k$: in OK rồi in cách gán màu cho từng biến.
• Nếu tổng số màu đã dùng $> k$: in SPILL rồi in số lượng biến có màu được gán $\ge k$ — đây chính là các biến phải "tràn" ra bộ nhớ (spill) vì không đủ thanh ghi vật lý.

Ví dụ: đồ thị tam giác đầy đủ $A,B,C$ (3 cạnh đôi một) với $k=3$: theo thứ tự gốc (cùng bậc 2), $A$ được tô trước, nhận màu $0$; $B$ kề $A$(màu 0) nên nhận màu $1$; $C$ kề cả $A,B$ nên nhận màu $2$ — dùng đúng 3 màu, đủ $k=3$ thanh ghi, in OK.