Trong một DFA, trạng thái không đạt được là trạng thái không thể tới được từ trạng thái bắt đầu bằng bất kỳ chuỗi nào. Chúng có thể loại bỏ mà không đổi ngôn ngữ. Hãy đếm và liệt kê các trạng thái không đạt được.
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
4 2
1 1
0 1
3 3
2 2
0
1 1
Output:
2
2 3
Khối mô tả DFA gồm:
n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.s.f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).1 ≤ n ≤ 10^5, 1 ≤ k ≤ 26.
Dòng 1: số trạng thái không đạt được. Dòng 2: danh sách các trạng thái đó theo thứ tự tăng dần (dòng trống nếu không có).
Ví dụ:
Đầu vào:
4 2
1 1
0 1
3 3
2 2
0
1 1
Đầu ra:
2
2 3
Giải thích:
Đang tải editor...