Bài tập | NEU OJ

Cho đồ thị giao (interference graph) gồm $n$ đỉnh $1,\ldots,n$ (đại diện biến/temporary) và $m$ cạnh vô hướng (hai biến sống đồng thời, không thể chung thanh ghi). Cho $k$ là số thanh ghi (màu) khả dụng. Mô phỏng thuật toán cấp phát thanh ghi kiểu Chaitin (simplify + spill, tô màu lạc quan) với các quy tắc CHÍNH XÁC sau (để đảm bảo kết quả đơn định):

Giai đoạn 1 — Simplify/Spill (xây ngăn xếp): Lặp lại trên đồ thị hiện tại (loại dần các đỉnh đã đẩy vào ngăn xếp cùng cạnh của chúng) cho đến khi rỗng:

Nếu tồn tại đỉnh bậc (degree trong đồ thị hiện tại) $< k$ : chọn đỉnh bậc nhỏ nhất trong số đó; nếu nhiều đỉnh cùng bậc nhỏ nhất, chọn đỉnh có số hiệu nhỏ nhất. Đẩy vào ngăn xếp, loại khỏi đồ thị hiện tại.
Nếu KHÔNG có đỉnh nào bậc $< k$ : chọn đỉnh có số hiệu nhỏ nhất trong các đỉnh còn lại (ứng viên tràn — potential spill), vẫn đẩy vào ngăn xếp, loại khỏi đồ thị hiện tại.

Giai đoạn 2 — Select (gán màu, pop theo LIFO): Lấy lần lượt từng đỉnh ra khỏi ngăn xếp (đỉnh đẩy vào SAU CÙNG được xử lý TRƯỚC). Với đỉnh $v$ : xét các láng giềng của $v$ trong đồ thị GỐC đã được xử lý trước đó (đã có màu, không phải SPILL); chọn màu nhỏ nhất trong $\{1,\ldots,k\}$ chưa bị láng giềng nào dùng. Nếu có màu như vậy: gán màu đó. Nếu không còn màu trống: đỉnh này TRÀN (SPILL).

In ra $n$ dòng theo thứ tự đỉnh $1,\ldots,n$ : số màu ( $1..k$ ) được gán, hoặc SPILL nếu tràn.

Ví dụ

Input:

(tam giác 3 đỉnh, chỉ có 2 màu — không đủ tô đúng, phải tràn 1 đỉnh)

Output:

SPILL
2
1

Định dạng đầu vào:
Dòng đầu: 3 số nguyên $n, m, k$ ( $1 \le n \le 300$ , $0 \le m \le 20000$ , $1 \le k \le n$ ). $m$ dòng tiếp theo " $u$ $v$ " ( $1 \le u, v \le n$ , $u \ne v$ ) là cạnh vô hướng (không có cạnh lặp).
Định dạng đầu ra:
In $n$ dòng theo thứ tự đỉnh $1,\ldots,n$ : số màu ( $1..k$ ) hoặc SPILL.

solution

Đề bài: [Trình biên dịch] Mô phỏng cấp phát thanh ghi bằng tô màu đồ thị kiểu Chaitin

Ví dụ