Đồ thị xáo trộn
Đề bài
Mô tả
Hãy cùng xem lại một bài toán rất cơ bản của lý thuyết đồ thị: cho một đồ thị vô hướng liên thông gồm đỉnh (đánh số từ đến ), thứ tự duyệt theo chiều sâu (DFS) của đồ thị là gì? Thứ tự DFS có thể được sinh ra bởi đoạn mã giả sau:
dfs_order = [] # danh sách rỗng
def DFS(u):
visited[u] = True
dfs_order.append(u)
for vertex v that is directly connected to u:
# lưu ý: thứ tự duyệt các đỉnh v là hoàn toàn ngẫu nhiên
if visited[v] == False:
DFS(v)
DFS(random(1,n))
Ví dụ, đồ thị đỉnh với các cạnh , , , có thứ tự DFS hợp lệ:
- 1, 2, 4, 3
- 1, 3, 2, 4
- 1, 3, 4, 2
- 1, 4, 2, 3
- 2, 1, 3, 4
- 2, 1, 4, 3
- 2, 4, 1, 3
- 3, 1, 2, 4
- 3, 1, 4, 2
- 4, 1, 2, 3
- 4, 1, 3, 2
- 4, 2, 1, 3
Cho một hoán vị của đến , hãy đếm xem có bao nhiêu đồ thị vô hướng nhận hoán vị này là một thứ tự DFS hợp lệ. Lưu ý rằng hai đồ thị và được coi là khác nhau khi và chỉ khi tồn tại hai đỉnh và () sao cho có cạnh nối và còn thì không, hoặc ngược lại.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên (), số đỉnh.
- Dòng thứ hai chứa số nguyên biểu diễn một thứ tự DFS. Dữ liệu bảo đảm là một hoán vị của .
Dữ liệu ra
In ra số đồ thị nhận hoán vị đã cho là thứ tự DFS, lấy theo modulo .
Ràng buộc
- là một hoán vị của .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 1 |
1 | Chỉ có một đồ thị là đồ thị đầy đủ (một cạnh ) nhận là thứ tự DFS. |
| 3 3 1 2 |
3 | Có đồ thị nhận là thứ tự DFS: các cạnh , và . |
Bình luận