Bài tập | NEU OJ

Cho đồ thị điều khiển luồng (CFG) gồm $n$ khối cơ bản đánh số $1,\ldots,n$ và $m$ cạnh có hướng $u \to v$ . Có $E$ biểu thức đánh số $1,\ldots,E$ . Với mỗi khối $B$ , cho trước:

$GEN[B]$ : tập biểu thức được tính tại $B$ và còn "sống" (chưa bị vô hiệu) đến cuối khối.
$KILL[B]$ : tập biểu thức bị vô hiệu tại $B$ (một trong các toán hạng của biểu thức bị gán lại trong $B$ ).

Tính tập biểu thức khả dụng (available expressions) — bài toán "must" (giao các nhánh) — bằng phương trình lặp điểm bất động chuẩn: $IN[B] = \bigcap_{P \in pred(B)} OUT[P] \qquad (IN[B] = \varnothing \text{ nếu } B \text{ không có tiền tố nào})$ $OUT[B] = GEN[B] \cup (IN[B] \setminus KILL[B])$

Khởi tạo $OUT[B] = \{1,\ldots,E\}$ với mọi $B$ , lặp lại cho đến khi mọi $OUT[B]$ không còn thay đổi (thuật toán đơn điệu, luôn hội tụ về nghiệm nhỏ nhất — chính là nghiệm đúng của bài toán).

In ra $n$ dòng, dòng thứ $B$ là các chỉ số biểu thức thuộc $OUT[B]$ sau khi hội tụ, theo thứ tự tăng dần, cách nhau dấu phẩy (không khoảng trắng); nếu rỗng in -.

Ví dụ

Input:

(3 khối, 2 biểu thức, cạnh $1\to2$ , $2\to3$ ; khối 1: $GEN=\{1\}, KILL=\varnothing$ ; khối 2: $GEN=\{2\}, KILL=\{1\}$ ; khối 3: $GEN=\varnothing, KILL=\varnothing$ )

Output:

1
2
2

Định dạng đầu vào:
Dòng đầu: 3 số nguyên $n, E, m$ ( $1 \le n \le 200$ , $1 \le E \le 60$ , $0 \le m \le 2000$ ). $m$ dòng tiếp theo, mỗi dòng " $u$ $v$ " là cạnh $u \to v$ ( $1 \le u, v \le n$ ). Tiếp theo, với mỗi khối $B = 1,\ldots,n$ theo thứ tự: một dòng gồm số nguyên $g$ (kích thước $GEN[B]$ ), $g$ chỉ số biểu thức, số nguyên $k$ (kích thước $KILL[B]$ ), rồi $k$ chỉ số biểu thức.
Định dạng đầu ra:
In $n$ dòng, dòng $B$ là $OUT[B]$ (chỉ số tăng dần, cách nhau dấu phẩy, không khoảng trắng); in - nếu $OUT[B]$ rỗng.

solution

Đề bài: [Trình biên dịch] Phân tích luồng dữ liệu: biểu thức khả dụng (Available Expressions)

Ví dụ