Sau khi sinh mã ba địa chỉ, chương trình được tổ chức thành các khối lệnh cơ bản (basic block) nối với nhau bởi các cạnh của đồ thị luồng điều khiển (Control Flow Graph — CFG), biểu diễn khả năng nhảy/rơi từ khối này sang khối khác (do lệnh goto/rẽ nhánh có điều kiện gây ra).
Một khối được gọi là không thể tới được (unreachable / dead) nếu không tồn tại đường đi có hướng nào từ khối entry (khối bắt đầu thực thi chương trình) tới nó trong CFG. Mọi lệnh TAC nằm trong các khối này không bao giờ được thực thi, do đó là mã chết (dead code) và có thể loại bỏ an toàn.
Cho CFG gồm n khối (đánh số 0,…,n−1), m cạnh có hướng, khối entry, và số lệnh TAC trong từng khối, hãy xác định: (1) tổng số lệnh còn hữu ích (nằm trong các khối tới được từ entry, kể cả entry); (2) danh sách các khối không thể tới được.
Dòng 1: hai số nguyên n, m (1≤n≤1000).
m dòng tiếp theo: mỗi dòng u v — cạnh có hướng từ khối u đến khối v (0≤u,v<n).
Dòng tiếp theo: số nguyên e — chỉ số khối entry.
Dòng cuối: n số nguyên c0 c1 … cn−1 — số lệnh TAC của từng khối theo thứ tự chỉ số.
Dòng 1: tổng số lệnh còn hữu ích (tổng ci với khối i tới được từ entry). Dòng 2: chỉ số các khối không tới được, liệt kê tăng dần, cách nhau một khoảng trắng (nếu không có khối nào không tới được, in một dòng trống).
Ví dụ:
Đầu vào:
1 0
0
5
Đầu ra:
5
Đầu vào:
3 2
0 1
1 2
0
2 3 4
Đầu ra:
9
Đang tải editor...