Với một tập ràng buộc phụ thuộc, thường có nhiều thứ tự khởi động hợp lệ khác nhau (các dịch vụ độc lập có thể đổi chỗ). Số thứ tự hợp lệ này gọi là số linear extension của thứ tự bộ phận.
Quan hệ A B nghĩa là A phải khởi động trước B. Hãy đếm xem có bao nhiêu thứ tự khởi động hợp lệ khác nhau của toàn bộ n dịch vụ.
3 dịch vụ a b c, không ràng buộc → mọi hoán vị đều hợp lệ → 6.
Dòng đầu là n, sau đó n dòng tên dịch vụ. Dòng tiếp là m, sau đó m dòng A B (A trước B).
1 ≤ n ≤ 12. Đồ thị không có chu trình.
Một số nguyên: số thứ tự khởi động hợp lệ khác nhau.
Ví dụ:
Đầu vào:
3
a
b
c
0
Đầu ra:
6
Giải thích:
Đang tải editor...