Nếu cày trâu, chọn tất cả các tập cạnh rồi xét tính liên thông của đồ thị và so với đồ thị gốc, ta có được thuật toán với độ phức tạp là \(O(2^m * (m+n))\) hoặc \(O(2^m * n^2)\).

Tuy nhiên đồ thị ở đây gần như là đồ thị đầy đủ nên \(m \leq nC2 \leq 36\) là quá lớn.

Bài toán này là bài toán đếm, ta có thể giải các bài toán đếm bằng QHĐ nếu như ta có trạng thái QHĐ phù hợp để biểu diễn bài toán.

Yêu cầu bài toán : Đếm số tập con các cạnh đồ thị sao cho các cạnh này tạo thành các TPLT giống với đồ thị gốc

Rõ ràng, để có thể QHĐ, trước hết ta phải có chiều [m] : Xét trong \(m\) cạnh đầu tiên.

Trạng thái còn lại phải biểu diễn được các TPLT --> Tại mỗi node ta sẽ lưu gốc của thành phần liên thông đang chứa nó.

Vậy trạng thái sẽ là

[m][r1][r2]...[rn]

Tuy nhiên nếu lưu như trên thì có vẻ như ta sẽ không đủ bộ nhớ, bởi vì gốc của TPLT nằm trong đoạn \([1..n]\) và ta lưu gốc của \(n\) đỉnh --> \(n^n\)

Để giải quyết, ta sẽ có một sự khéo léo trong cài đặt : khi ta lưu gốc của TPLT, ta chỉ lưu theo chỉ số của đỉnh nhỏ nhất trong TPLT này.

Vậy thì tại mỗi node \(i\), ta luôn đảm bảo được \(r_i \leq i\)

Vậy bộ nhớ ta cần dùng là \(O(n^2 * n!)\), vừa đủ.

ĐPT thời gian : Số bài toán nhân chi phí chuyển, chi phí chuyển ở đây là \(O(n)\), nếu tính sát sao thời gian \((36 * 9! * 9)\) thì vẫn kịp trong thời gian 2s.

Ở trên là những ghi chép của tôi lúc giải bài này. Nhằm phục vụ cho việc giải bài của các bạn, xin có một số lưu ý nhỏ :

• Khi chuyển trạng thái trong QHĐ, có 2 trường hợp : chọn cạnh thứ \(i\), hoặc không chọn cạnh thứ \(i\). Nếu chọn cạnh thứ \(i\), bạn chỉ cần cập nhật \(r_1,r_2,...,r_n\) trong \(O(n)\) phép tính.

• Đáp án bài toán là f[n][trạng thái liên thông của đồ thị gốc]